Binary tree — structure, traversals - preorder, inorder, postorder (recursive and iterative): Worked examples

This is the drill page for the parent topic. We will not learn new theory here — we will take the three orders (Pre = N L R, In = L N R, Post = L R N) and throw every shape of tree at them until nothing surprises you.

If any symbol below feels unfamiliar, the parent note builds it. Quick refresher of the only three words you need:

Node ::: a box holding a value with a left arrow and a right arrow (each pointing to another node or to nothing).
None / empty tree ::: an arrow that points to nothing; the base case where recursion stops.
Leaf ::: a node whose left and right are both None.

The scenario matrix

Before working examples, let's list every distinct shape a binary tree can take. If we cover one example of each row, no future tree can ambush you.

Cell	Case class	What is "degenerate" / special about it	Covered by
C1	Empty tree (`root = None`)	there is no node at all — zero input	Ex 1
C2	Single node (root only)	root is also a leaf; no children	Ex 2
C3	Full & balanced (both children everywhere)	the "textbook" symmetric case	Ex 3
C4	Left-skewed (only left arrows)	acts like a linked list going down-left	Ex 4
C5	Right-skewed (only right arrows)	linked list going down-right; stack depth = n	Ex 5
C6	Lopsided / mixed (some nodes miss one child)	the realistic messy case	Ex 6
C7	BST inorder = sorted?	the classic "inorder gives sorted" claim, tested	Ex 7
C8	Word problem (folder-size / free-memory)	why postorder exists in the real world	Ex 8
C9	Exam twist (reconstruct tree from two orders)	reverse the process	Ex 9
C10	Iterative-vs-recursive match	prove the explicit stack gives identical output	Ex 10

Each example tells you which cell it fills.

Ex 1 — The empty tree (C1)

Forecast: guess before reading. How many values can you print if there are no nodes?

Look at the recursion's first line: if node is None: return. Why this step? This is the whole answer. The very first thing every traversal does is check for None and bail out.
So nothing is appended. Output list stays empty for pre, in, and post. Why this step? There is no node, so there is no N to visit and no L/R to recurse into.

Verify: all three return []. Length $= 0 = n$ (the number of nodes). ✓ This is why the None base case is mandatory — it makes the zero-input case correct for free.

Ex 2 — A single node (C2)

Worked example Statement

root.val = 7, root.left = None, root.right = None. Give all three outputs.

Forecast: with one node, does the order (Pre/In/Post) even matter?

Preorder N L R: visit 7, recurse left (None → nothing), recurse right (None → nothing) → [7]. Why this step? N happens first, but L and R are both empty, so only N contributes.
Inorder L N R: left empty → visit 7 → right empty → [7].
Postorder L R N: both empty → visit 7 → [7].

Verify: all three give [7]. Sanity check: when a node has no children, all three orders collapse to the same single value — the position of N is irrelevant if there is nothing around it. ✓

Ex 3 — Full & balanced (C3)

This is the canonical tree. Look at the figure — the numbers on the arrows show the dive order your finger takes.

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

Worked example Statement

Give preorder, inorder, postorder.

Forecast: which traversal will print 1 first? Which prints it last? Which puts it in the middle?

Preorder (N L R): print each node the instant you arrive. Root 1, then whole left 2 4 5, then whole right 3 6 7.
- Order: 1 → (2 → 4 → 5) → (3 → 6 → 7) = 1 2 4 5 3 6 7. Why this step? N is printed before diving, so parents always precede their descendants.
Inorder (L N R): dive to the leftmost leaf 4 before printing anything.
- 4 2 5 (left subtree done) → 1 (root, middle!) → 6 3 7 = 4 2 5 1 6 3 7. Why this step? The root sits dead-center because exactly half the nodes (its left subtree) print before it.
Postorder (L R N): children before parent, everywhere.
- Left subtree 4 5 2, right subtree 6 7 3, then root 1 last = 4 5 2 6 7 3 1. Why this step? A parent prints only after both its subtrees are fully done → root is always last.

Verify: each output has 7 distinct values, each node once. In inorder, 1 is at index 3 — the exact middle of a 7-element list, matching a perfectly balanced tree. ✓

Ex 4 — Left-skewed tree (C4)

Worked example Statement

Only left arrows. Give all three.

Forecast: with no right children, R always recurses into None. Guess how much that simplifies things.

Every R is empty, so effectively pre = N L, in = L N, post = L N (R drops out). Why this step? Removing an always-empty step reveals the pure pre/post nature.
Preorder (N L): 3 → 2 → 1 = 3 2 1 (top-down).
Inorder (L N): dive to 1, then up: 1 → 2 → 3 = 1 2 3 (bottom-up).
Postorder (L N): deepest first: 1 → 2 → 3 = 1 2 3.

Verify: inorder and postorder are identical here (1 2 3) because with no right subtree, "node after left" (in) and "node after both children" (post) mean the same thing. Preorder is the exact reverse. ✓

Ex 5 — Right-skewed tree (C5, worst-case stack depth)

Worked example Statement

Only right arrows. Give all three and state the recursion depth.

Forecast: this is a "linked list" tree. How deep does the call stack get?

Every L is empty → pre = N R, in = N R, post = R N.
Preorder (N R): 1 → 2 → 3 = 1 2 3.
Inorder (L N R) = N R here: 1 → 2 → 3 = 1 2 3 (same as pre!). Why this step? With no left child, "node between L and R" places the node first, exactly like preorder.
Postorder (L R N) = R N: deepest first, 3 → 2 → 1 = 3 2 1.
Depth: the stack holds 1,2,3 simultaneously at the bottom → depth $= 3 = n$ . Why this step? Height $h = n$ for a skewed tree, so space $= O (h) = O (n)$ — the worst case from the parent note.

Verify: pre = in = 1 2 3, post = 3 2 1. Stack depth equals $n = 3$ , confirming $O (n)$ space for skewed trees. ✓

Ex 6 — Lopsided, mixed missing children (C6)

This is the messy realistic case. The figure shows nodes that are missing one child (dashed empty slots).

Worked example Statement

3 has only a right child; 8 has only a right child; 4 has only a left child. Give all three.

Forecast: this is where careless people slip. Trust the recipe N/L/R exactly at every node, even the one-child ones.

Preorder (N L R) — print on arrival, always try left before right (empty just returns):
- 5 → left into 3: print 3, left empty, right 4: print 4, left 2: print 2, (2's children empty), 4's right empty, back up.
- → right of 5 is 8: print 8, left empty, right 9: print 9.
- Result: 5 3 4 2 8 9.
Inorder (L N R) — leftmost first:
- Under 3: left empty so print 3; its right 4 has left 2 → print 2, then 4. So subtree order: 3 2 4.
- Then root 5.
- Under 8: left empty → print 8, then right 9. So: 8 9.
- Result: 3 2 4 5 8 9. Why this step? At node 3, left is empty, so "L done" instantly → we print 3 before descending into its right child 4.
Postorder (L R N) — parent last:
- Under 3: 4's subtree first (2 then 4), then 3. So: 2 4 3.
- Under 8: 9 then 8.
- Root 5 last.
- Result: 2 4 3 9 8 5.

Verify: all three lists contain exactly {2,3,4,5,8,9} — 6 nodes, each once. Preorder starts with 5, postorder ends with 5 (the root). ✓

Ex 7 — Does inorder always give sorted output? (C7)

Worked example Statement

Compare inorder on two trees holding the same values {2,1,3}: Tree A (a valid Binary Search Tree):

    2
   / \
  1   3

Tree B (a plain binary tree, NOT a BST):

    3
   / \
  1   2

Is inorder sorted in both?

Forecast: the parent note's Mistake #2 warns about this. Predict before computing.

Inorder of Tree A (L N R): 1 → 2 → 3 = 1 2 3 → sorted. Why this step? In a BST, for every node all left-subtree values are smaller and all right-subtree values are larger. L-N-R therefore emits them ascending.
Inorder of Tree B (L N R): left 1 → root 3 → right 2 = 1 3 2 → NOT sorted. Why this step? Tree B violates the BST rule (2 sits to the right of 3 but is smaller). Inorder just does L-N-R faithfully; it has no idea about ordering.

Verify: Tree A → [1,2,3] (sorted); Tree B → [1,3,2] (not sorted). Conclusion: inorder ⇒ sorted only for a BST, exactly as the parent's steel-man warned. ✓

Ex 8 — Word problem: computing folder sizes (C8)

Worked example Statement

A file system is a binary tree. A leaf is a file with a size; an internal node is a folder whose size = sum of its children's sizes. Compute the size printed at the root, and state which traversal you must use.

       Root(?)
       /     \
     A(?)     B(5)
     /  \
  C(2)   D(4)

B, C, D are files (leaves) with sizes 5, 2, 4. A and Root are folders.

Forecast: to know a folder's size you need its children's sizes first. Which order guarantees children are processed before parents?

Choose postorder (L R N). Why this step? Postorder is the only order where a node is processed after both children — precisely when the children's sizes are already known.
Process leaves first: C = 2, D = 4, B = 5 (given).
Process A (after C, D): A = C + D = 2 + 4 = 6. Why this step? We reach A in postorder only once C and D are done, so their sizes exist.
Process Root (after A, B): Root = A + B = 6 + 5 = 11.

Verify: total of all files = $2 + 4 + 5 = 11$ = Root size. Units: all in the same "size" unit (say KB), summed → KB, consistent. ✓ This is the real reason postorder exists: bottom-up aggregation (also how you free() a tree — children before parent).

Ex 9 — Exam twist: reconstruct the tree (C9)

Forecast: preorder's first element is special. What is it, and what does inorder let you split?

Root = first of preorder = 1. Why this step? Preorder is N-L-R, so the very first visited node is the root.
Split inorder at 1: left part [4,2,5], right part [3]. Why this step? Inorder is L-N-R, so everything before the root in inorder is the left subtree, everything after is the right subtree.
Left subtree has 3 nodes; take the next 3 from preorder after 1: [2,4,5]. Its root is 2 (first). Split its inorder [4,2,5] at 2 → left [4], right [5]. So 2 has left child 4, right child 5.
Right subtree inorder [3], preorder remainder [3] → single node 3.
Reconstructed tree:
```
      1
     / \
    2   3
   / \
  4   5
```
(Exactly the parent note's worked-example tree!)
Postorder (L R N): 4 5 2 3 1.

Verify: running inorder on the rebuilt tree gives 4 2 5 1 3 ✓ and preorder gives 1 2 4 5 3 ✓ — both match the given inputs, so the reconstruction is correct. (See Construct Tree from Preorder + Inorder for the general algorithm.)

Ex 10 — Recursive == Iterative (C10)

Forecast: the parent claims recursion is a hidden stack. Watch the stack contents step by step and predict each pop.

Start: stack = [1], out = []. Why this step? We seed the stack with the root, mirroring the first recursive call.
Pop 1, visit → out=[1]. Push right 3, then left 2 → stack=[3,2]. Why push right first? A stack is LIFO: pushing 2 last puts it on top so it pops next — giving N L R order. (Parent Mistake #1.)
Pop 2, visit → out=[1,2]. Push 5 then 4 → stack=[3,5,4].
Pop 4 (leaf), visit → out=[1,2,4]. stack=[3,5].
Pop 5 (leaf) → out=[1,2,4,5]. stack=[3].
Pop 3, visit → out=[1,2,4,5,3]. Push 7 then 6 → stack=[7,6].
Pop 6, pop 7 → out=[1,2,4,5,3,6,7]. Stack empty → stop.

Verify: iterative output 1 2 4 5 3 6 7 = recursive preorder from Ex 3. ✓ The explicit stack reproduced the exact ancestor-chain the Recursion and the Call Stack would have held.

Recall Which traversal for which job?

Copy/print a tree preserving structure ::: preorder (root first, then children)
Get sorted values out of a BST ::: inorder
Delete/free a tree, or compute folder sizes bottom-up ::: postorder
Rebuild a tree from two orders — which order gives the root? ::: preorder's first element (or postorder's last)

See also Tree Height and Balance (why space is $O (h)$ ) and Level-order Traversal (BFS) (the non-DFS alternative that uses a queue instead of a stack).