Tree Traversal

A binary sort tree keeps smaller items on the left and larger items on the right of every node. Because of that rule, it is tempting to assume that searching for an item and inserting an item will always be fast. The placement rule is sound, but the speed of both operations depends on something the placement rule alone does not guarantee: the overall shape of the tree. This article starts from that assumption, shows exactly where it breaks, and then builds the search, insertion, and counting procedures so you can see which step depends on shape.

A search begins by comparing the item you want with the root item. There are three possible outcomes. If the two are equal, the search is finished and the item has been found. If the item is less than the root, only the left subtree can contain it, so the right subtree can be thrown away. If the item is greater than the root, only the right subtree needs to be examined, and the left subtree can be thrown away. The same procedure is then applied to whichever subtree remains.

Notice what a single comparison buys. One comparison at a node does not merely test one item. It removes an entire subtree from further consideration. When the tree is balanced, each comparison removes about half of the remaining items, which is the same pattern used by binary search on a sorted list. That is why a balanced tree gives a similarly efficient search, and why an unbalanced tree does not.

Insertion is similar to search. The procedure first searches the tree for the position where the new item belongs. The path it follows is exactly the path a search for that item would follow. When the search falls off the tree at an empty spot, a new node is created and attached at that place. In other words, the new node takes the position of the empty link where the search would have ended.

Inserting 25 into the generated tree from the search example follows the same path as the failed search. 25 is less than 50, so it moves left to 30. It is less than 30, so it moves left to 20. It is greater than 20, and the right side of 20 is empty, so a new node holding 25 is attached there. The new node is a leaf, and every other node keeps its position.

A binary tree is balanced when, for each node, the left subtree has approximately the same number of nodes as the right subtree. In a perfectly balanced tree those two counts differ by at most one. Not every binary tree is balanced. If items are inserted in a random order, there is a high probability that the tree comes out approximately balanced. If the order of insertion is not random, the tree can become very unbalanced.

The chain is the extreme case, and it shows why the balance matters. Every node has an empty left subtree, so each comparison removes only one item from consideration instead of about half of the remaining items. With three values the difference looks small, but with a long list of insertions in sorted order, the search path grows with the number of items. The efficient behavior described for binary search trees depends on balance, and balance depends on the insertion order.

Any non-empty binary tree can be viewed as three pieces: a root node, a left subtree, and a right subtree. Either subtree, or both, may be empty. In the six-node tree used throughout this article, the root has node 2 as the top of its left subtree, and node 2 together with its descendants 4 and 5 forms that subtree. Node 3 and its descendant 6 form the right subtree of the root. The root itself is not part of either subtree.

This description is recursive, because it refers to smaller binary trees inside its own definition. A tree is defined in terms of trees. The shape matches the recursive definition of the TreeNode class used in code, where each node refers onward to its left and right children. Since the data and the definition have the same shape, a subroutine that handles a tree can naturally call itself on the smaller pieces, which is why recursive subroutines are so often used to process trees.

Counting the nodes of a binary tree looks simple, but a single straight-line pass is awkward. Each node can lead to two branches, and once you move down one branch you must still remember that the other branch exists. Recursion handles this bookkeeping automatically. The recursive rule is almost trivial: the count for an empty tree is zero, which is the base case that stops the recursion. For a tree with a root, the count is the number of nodes in the left subtree, plus the number in the right subtree, plus one for the root itself.

A recursive count does not finish in one visible step. Each call starts another call on a smaller subtree, and it cannot produce its own answer until the calls beneath it have returned. Empty subtrees are left out of the diagram below, because each of them returns zero immediately. Read the diagram from the top: the call for the root begins first, and the results travel back up as each call finishes.

No loop has to keep a list of pending branches. The call stack that the language already maintains holds that bookkeeping. Each call waits for the calls beneath it, and each return value is added to a running total at the level above.