Exercises — Binary tree — structure, traversals - preorder, inorder, postorder (recursive and iterative)

Preorder is N L R: print the node the instant you arrive, then dive fully left, then right.

• Visit 1 (root). → [1]
• Go left into subtree rooted at 2. Visit 2. → [1,2]
• Go left into 4. Visit 4. 4 has no children. → [1,2,4]
• Back to 2, go right into 5. Visit 5. Leaf. → [1,2,4,5]
• Left subtree of 1 done. Go right into 3. Visit 3. → [1,2,4,5,3]
• 3 has a right child 6. Visit 6. Leaf. → [1,2,4,5,3,6]

Answer: 1 2 4 5 3 6.

Inorder is L N R: never print a node until its entire left subtree is finished.

• From 1, dive left to 2, keep diving left to 4. 4 has no left child → visit 4. → [4]
• 4 has no right child. Back up to 2. Its left is done → visit 2. → [4,2]
• Go right of 2 into 5. No left child → visit 5. → [4,2,5]
• Left subtree of 1 fully done → visit 1. → [4,2,5,1]
• Right of 1 is 3. 3 has no left child → visit 3. → [4,2,5,1,3]
• Right of 3 is 6 → visit 6. → [4,2,5,1,3,6]

Answer: 4 2 5 1 3 6.

Postorder is L R N: a node is printed last, only after both its children's whole families are done.

• Deepest-left first: 4 (no children) → [4].
• 5 (no children) → [4,5].
• Both children of 2 done → 2 → [4,5,2].
• Right subtree of 1: dive to 3. 3 has no left, right is 6. Visit 6 first → [4,5,2,6].
• Both children of 3 done → 3 → [4,5,2,6,3].
• Finally the root 1 → [4,5,2,6,3,1].

Answer: 4 5 2 6 3 1.

Algorithm: pop, visit, then push right first, then left so left pops next.

• Start: stack = [1].
• Pop 1, visit → out [1]. Push right 3, then left 2. stack = [3, 2] (top is 2).

Answer: immediately after visiting 1, stack = [3, 2] with 2 on top. Continuing pops 2 next, exactly what preorder wants. Full output: 1 2 4 5 3 6.

With no children, L and R both hit the None base case and do nothing. Only N fires.

• Preorder = N (L,R empty) = 7.
• Inorder = (L empty) N (R empty) = 7.
• Postorder = (L,R empty) N = 7.

Answer: all three are 7. Degenerate case: order of N/L/R can't matter when there's only an N.

We must be precise about what is returned. In the list-building traversals used on this page (the ones that build and return an output list, like preorder_iter), the base case is return [] — an empty list, not None. So the traversal of an empty tree is the empty list [], which is the correct, safe answer to append to or iterate over.

(In the recursive void helpers of the parent note, written as def preorder(node, out): if node is None: return, the bare return simply stops that call without appending anything — the accumulated out list stays empty. Same observable result: no values are produced.)

Answer: the traversal yields the empty list [] for all three (never None). This base case is what makes recursion terminate at all — remove it and you crash on None.left.

No node has a left child, so every L recursion is empty.

• Preorder N L R: N then (skip L) then R. So 1, then into 2: 2, then 3, then 4 → 1 2 3 4.
• Inorder L N R: L empty each time, so it's just N then R, same as preorder → 1 2 3 4.
• Postorder L R N: go all the way right to 4 (deepest), print it, back up printing each → 4 3 2 1.

Answer: Pre = 1 2 3 4, In = 1 2 3 4, Post = 4 3 2 1. Note preorder and inorder coincide here — with no left children there's nothing to sit "before" the node. Using the definitions above, $n=4$ nodes and the longest root-to-leaf path is 1→2→3→4 = three edges, so $h=3=n-1$ — the maximally unbalanced ("skewed") shape. See Tree Height and Balance.

Key facts. Preorder's first element is always the root. In inorder, everything left of the root is the left subtree, everything right is the right subtree.

• Preorder starts with A → root is A.
• In inorder D B E | A | C F: left subtree = {D,B,E}, right subtree = {C,F}.
• Left subtree's preorder (next 3 items) = B D E. Root of left = B. Its inorder D | B | E → left child D, right child E.
• Right subtree's preorder = C F. Root = C. Its inorder C F → C has no left (nothing before C), right child F.

Resulting tree:

        A
       / \
      B   C
     / \    \
    D   E    F

Check (regenerate): preorder = A B D E C F ✓, inorder = D B E A C F ✓.

At any single instant during a DFS traversal, the call stack (or explicit Stack (LIFO)) holds only the chain of ancestors from the root down to the node you're currently at — one frame per level. You never hold two siblings' full recursions simultaneously: you finish the left recursion (which pops all its frames) before starting the right. So the maximum stack depth = the longest root-to-node path = the height $h$.

• Balanced tree: $h\approx {\log }_{2}n$ → space $O(\log n)$.
• Skewed tree (L2.4): $h=n-1$ → space $O(n)$.

Answer: space is $O(h)$ because only one ancestor chain is live at a time. (See Recursion and the Call Stack.)

You must free children before the parent, otherwise you'd lose the pointers to the children after deleting the parent. That is exactly L R N — postorder. Preorder would free the parent first and orphan the subtrees; inorder frees the right subtree after the parent, same problem.

Answer: Postorder.

Inorder L N R, diving leftmost first:

• Leftmost is 1 → 1. Back to 3 → 3. Right of 3 is 6 → 6. → [1,3,6]
• Root 8 → [1,3,6,8].
• Right subtree of 8: 10 has no left → 10, then right 14 → 14. → [1,3,6,8,10,14]

Answer: 1 3 6 8 10 14 — sorted ascending. Why sorted: in a BST, everything in a node's left subtree is smaller and everything in its right subtree is larger. Inorder visits (all-smaller) → node → (all-larger), which is precisely ascending order. This is a BST property, not a property of inorder on arbitrary trees (parent-note mistake #2).

We start from the literal two-stack postorder and change only the "collect" line. In the original, when we pop a node from s1 we append its value to s2; here, at that same moment, we instead test whether the node is a leaf. Because postorder's two-stack pass still visits every node exactly once (that fact is independent of the reversal step), the leaf count is correct.

def count_leaves(root):
    if root is None: return 0
    s1, cnt = [root], 0        # s1 is the SAME driver stack as two-stack postorder
    while s1:
        node = s1.pop()
        # original two-stack line was:  s2.append(node.val)
        # we swap it for the leaf test at the same visit moment:
        if node.left is None and node.right is None:
            cnt += 1
        if node.left:  s1.append(node.left)   # same push order as postorder driver
        if node.right: s1.append(node.right)
    return cnt

The s2 stack (and its final reversal) is simply dropped, because a count doesn't care about the visit order — only that each node is seen once. For s01: nodes 4, 5, 6 have no children → 3 leaves. (1, 2, 3 each have at least one child.)

Answer: 3.

Preorder goes depth-first (dive to a leaf before exploring siblings). Level-order goes breadth-first (finish a whole level before descending). They agree only when "go deep" and "go wide" are the same walk — i.e. when there's never a choice, meaning every level has at most one branching that keeps depth = breadth order.

The cleanest guaranteed case: a right-skewed (or any single-child) chain, like L2.4's 1→2→3→4. Preorder = 1 2 3 4 and level-order = 1 2 3 4. They diverge the instant a node has two children whose subtrees have depth > 1.

Answer: They coincide for a degenerate chain (each node has ≤1 child); in general they differ because preorder is DFS and level-order is BFS.

First, two plain-word definitions so no symbol is unearned:

• Concatenation of two lists means "write the first list, then the second, end to end." We write it with a plus sign here: [a] + [b, c] means the list [a, b, c].
• Reversal of a list means "read it back to front": reversing [a, b, c] gives [c, b, a]. A useful rule: reversing a concatenation flips the block order and reverses each block, so reverse of (X + Y) equals (reverse of Y) + (reverse of X).

Let M(x) be the output of the modified pass on the subtree rooted at node x, whose left subtree is Lx and right subtree is Rx. The modified pass visits the root first, then recurses right, then left:

M(x) = [x] + M(Rx) + M(Lx) (root, then all of right, then all of left)

Now reverse both sides, applying the rule above (flip order, reverse each block):

reverse(M(x)) = reverse(M(Lx)) + reverse(M(Rx)) + [x]

Argue by induction (assume it already holds on the smaller subtrees Lx and Rx): if reverse(M(Lx)) equals the true postorder of Lx, and likewise for Rx, then

reverse(M(x)) = postorder(Lx) + postorder(Rx) + [x]

which is exactly the definition of postorder L R N (left subtree, then right subtree, then the node). Base case: an empty subtree gives the empty list both ways, so the claim holds there too. That completes the proof.

Answer: proven — reversing a "root, right, left" walk yields "left, right, root", i.e. postorder.

The algorithm (parent note) does three repeating jobs: (1) dive left pushing every node, (2) pop and visit, (3) turn right. Here every node's right child is None, so step (3) never adds anything new.

• Dive left: push 4, then 3, then 2, then 1. Now cur = None and stack = [4, 3, 2, 1] with 1 on top. This is the deepest the stack ever gets: max stack depth = 4, which equals $n=4$ and $h+1=4$ (the full ancestor chain is live at once).
• Pop/visit/turn-right: pop 1, visit → [1]; 1.right is None, so loop pops again.
• Pop 2, visit → [1,2]; right None. Pop 3 → [1,2,3]. Pop 4 → [1,2,3,4]. Stack empty, done.

Answer: output 1 2 3 4; maximum stack depth 4. This realises the worst-case space $O(h)=O(n)$ for a skewed tree — the concrete illustration of L3.2.

• Preorder N L R: 5, left 3,2, right 8,7,9 → 5 3 2 8 7 9.
• Inorder L N R: leftmost 2, then 3, back to 5, then right subtree inorder 7 8 9 → 2 3 5 7 8 9.
• Postorder L R N: 2 then 3 (its only child done); right subtree 7 9 8; root 5 last → 2 3 7 9 8 5.
• Level-order Traversal (BFS) (queue, level by level): 5 | 3 8 | 2 7 9 → 5 3 8 2 7 9.

Answers: Pre = 5 3 2 8 7 9, In = 2 3 5 7 8 9, Post = 2 3 7 9 8 5, Level = 5 3 8 2 7 9. (Notice inorder is sorted — because this happens to be a valid Binary Search Tree.)