Noesis
3.4.2 · D5Trees

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

1,496 words7 min read↑ Back to topic

These are the traps your brain wants to fall into. Cover each answer, say yours out loud, then reveal. Every answer here is reasoning, not a bare verdict. Parent: Binary Tree — Traversals.

Before you start, two words we use constantly are defined in plain language so nothing is assumed:

True or false — justify

True or false: Inorder traversal of ANY binary tree produces a sorted list.
False. Sorted output comes from the Binary Search Tree ordering property (left < node < right), not from inorder itself. On a random tree, inorder just gives L-N-R in whatever order the values happen to sit.
True or false: Preorder and postorder are just reverses of each other.
False. Preorder is N L R; postorder is L R N. Reversing postorder gives N R L (root first but right before left), which is not preorder. Only N L R reversed vs N R L reversed lines up — and neither is the other traversal.
True or false: Every traversal visits each node exactly once.
True. All three DFS orders and BFS touch each of the nodes one time; that is why all are time. What differs is only when the visit is recorded, not how many times.
True or false: For a tree with only a root and no children, all three traversals give the same output.
True. With no left or right subtree, N L R, L N R, and L R N all collapse to just N — a one-element list [root]. The orderings only diverge once children exist.
True or false: Iterative and recursive versions of the same traversal always output the identical sequence.
True. The iterative version merely makes the hidden call stack explicit; the visit order is a property of the traversal definition, not of how you implement it.
True or false: A stack is the wrong data structure for BFS (level-order).
True. BFS needs first-in-first-out (a queue), because you must finish the earliest-discovered level first. A stack is LIFO and would send you diving deep — that gives DFS, not BFS.
True or false: If a node has a right child but no left child, inorder still "dives left first."
True in spirit. Inorder always tries to go left; here cur.left is None, so the dive stops immediately, the node is visited, and we turn right. The rule "left fully first" holds vacuously when there is no left subtree.
True or false: The space cost of recursive traversal depends on the number of nodes .
False. It depends on the height , i.e. , because the stack only ever holds the ancestor chain from root to the current node — at most one node per level, not all . See Tree Height and Balance.

Spot the error

Someone writes iterative preorder pushing left before right. What breaks?
A stack is LIFO, so the last thing pushed pops first. Pushing left first means right pops first, giving N R L — wrong. Fix: push right first so left is on top.
A recursion has no if node is None: return. Where does it crash?
At a leaf. A leaf's .left/.right are None, and the code still recurses into them, then tries None.left → AttributeError. The None check is the base case that stops the descent.
Someone claims postorder is "right child, then left child, then root."
Wrong swap. Postorder is L R N — left subtree before right subtree, root last. "R then L then N" reverses the two children.
Iterative inorder loops on while cur: only (no and stack / or stack). Bug?
It exits the moment cur becomes None after the deepest left dive, never popping the stacked ancestors. The loop must be while cur or stack: so we keep going while there are still parked ancestors to visit.
Postorder two-stack code forgets the final s2[::-1]. What's the output?
You get N R L order (root, right, left) instead of postorder. The reversal is the whole trick: reversing N R L yields L R N = postorder.
In iterative inorder someone visits the node before diving left (out.append before the while cur loop). Result?
That produces preorder-ish behaviour, not inorder. Inorder must visit on the way back up, after the left subtree is exhausted — the append belongs after stack.pop().

Why questions

Why does recursion "just work" for trees?
Because a tree is self-similar: each subtree is itself a full binary tree. The recursive call structure mirrors the data structure exactly, so "process node + recurse left + recurse right" is the literal definition. See Recursion and the Call Stack.
Why is the only difference between the three traversals the position of N?
L always precedes R by convention, so the sole free choice is when you record the current node: before children (N L R), between them (L N R), or after (L R N). That one placement is the entire topic.
Why is iterative preorder easier than iterative inorder?
Preorder visits a node the instant it's popped, so a plain stack with push-right-then-left suffices. Inorder must delay the visit until the left subtree is done, so you need the extra "dive left, stash, pop, turn right" dance.
Why is postorder the natural order for freeing/deleting a tree?
It processes all descendants before the parent (L R N), so children are released before the parent that points to them — you never free a node whose subtrees still need visiting.
Why does reversing "Root-Right-Left" give postorder?
Reverse of the sequence N R L is L R N, which is exactly postorder. The two-stack trick exploits this: build the easy N R L order, then flip it.
Why is space and not ?
At any instant the stack holds only the ancestors on the path from root to the current node — one per level, at most of them. The already-visited and not-yet-reached nodes are not on the stack.

Edge cases

What do all traversals return for an empty tree (root is None)?
An empty list []. The base case fires immediately; no node is ever visited, which is exactly correct — there is nothing to visit.
For a completely left-skewed tree (every node has only a left child), what is inorder?
The values from the deepest (bottom-left) node up to the root, i.e. reversed depth order. The height is , so recursion/stack space degrades to — the worst case. See Tree Height and Balance.
For a right-skewed tree (only right children), how do preorder and inorder compare?
They give the same sequence (top node down to bottom). With no left subtrees, N L R and L N R both reduce to N R, so root-then-right repeats identically all the way down.
Can you rebuild a tree from just its preorder list alone?
No. Preorder alone is ambiguous — many shapes give the same list. You need a second traversal, classically preorder plus inorder, to pin down the structure. See Construct Tree from Preorder + Inorder.
If a single traversal (say inorder) is given for a tree where every node has one child, is the shape recoverable?
No. You cannot tell whether each single child was a left or a right child from one traversal; the sequence is consistent with many shapes. A second traversal is required.
What happens to the two-stack postorder on a single-node tree?
s1=[root] pops the root into s2, pushes nothing (no children), loop ends, and s2[::-1] is [root]. Correct: a lone node is its own postorder.