Binary Tree Traversals
A binary tree is either empty or a root with a left and a right subtree, so almost every tree algorithm is divide-and-conquer: solve both subtrees, then combine. Build a tree, pick an algorithm and watch the recursion.
How to read this
Circles are the tree's real (internal) nodes. Squares □ are external nodes: they stand for the empty subtrees hanging below. Together they form the extended tree, and there is always exactly one more square than circle: x = n + 1.
Colors. Blue is the call running right now. Purple nodes are waiting on the recursion stack (their call started but hasn't finished). Green nodes have been visited (output) or have returned. A yellow square is a call on an empty subtree, which returns at once.
Numbers. For the traversals, the small number under a node is its position in the output. For Height and Leaf count, the number next to a node or square is the value its call returned (−1 for an empty tree's height).
Counters. Every recursive traversal makes one call per internal and external node: C(n) = n + x = 2n + 1 checks of "T = ∅". Height also does n additions, one per internal node (Levitin §5.3).
Try this
- With the a…g preset, predict all three orders before playing. Check: preorder a b d g e c f, inorder d g b e a f c, postorder g d e b f c a.
- Build a BST from any keys and run inorder: the output is sorted. That's Levitin Exercise 5.3.7.
- Grow the tree by clicking squares. After every click, check n, x and the "T = ∅ checks" counter after a full run: 2n + 1 every time.
- Load the chain. Its height is n − 1 = 4, the worst possible. The balanced BST with 7 nodes has height 2. Which one would you rather search?
- Run Height on the empty tree and on a single node: −1 and 0. Why is −1 the right answer for ∅? (Hint: a single node must get max(−1, −1) + 1 = 0.)