Micro-questions over the depth-first traversals module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
The reference tree throughout:
1
/ \
2 3
/ \
4 5
A. The vocabulary
1. What is a traversal?
Answer
Visiting every node in a tree exactly once, in some definite order. The tree does not change; what changes is the sequence in which you see the nodes.
2. What is a “visit”?
Answer
The moment you actually do something with a node — print it, append it, compare it. The whole difference between traversal orders is when the visit happens relative to the recursive calls.
3. What is depth-first traversal, and what does it use?
Answer
Going as deep as possible down one branch before backing up. It uses a stack — either an explicit one or the call stack recursion provides.
4. What is breadth-first traversal, and what does it use?
Answer
Visiting every node at one depth before moving down. It uses a queue. Also called level-order.
5. Define pre-order, in-order and post-order in terms of where the visit sits.
Answer
Pre-order: node first, then left, then right.
In-order: left, then node, then right.
Post-order: left, then right, then node last.
6. What is the call stack?
Answer
The private memory the language uses to remember where it was — a record per call saying which line to return to and what the locals were. Recursion is not magic; it is a stack you did not have to write.
7. What is an explicit stack, and why would you write one?
Answer
A stack you create yourself, usually a list. It lets you do the same traversal without recursion — which matters because the call stack is small and fixed while a list can grow as large as memory allows.
8. What does “iterative” mean here?
Answer
Written as a loop rather than a function calling itself. Every recursive traversal has an iterative twin doing exactly the same work; the difference is only who keeps track of where you were.
B. The three recursive orders
9. Write pre-order recursively.
Answer
def preorder(node, result):
if node is None: return
result.append(node.val)
preorder(node.left, result)
preorder(node.right, result)10. What do the three recursive functions have in common?
Answer
Exactly the same three lines. The only thing that moves is where the visit line sits — and that single difference is the entire topic.
11. Pre-order output on the reference tree?
Answer
[1, 2, 4, 5, 3]
12. In-order output on the reference tree?
Answer
[4, 2, 5, 1, 3]
13. Post-order output on the reference tree?
Answer
[4, 5, 2, 3, 1]
14. What is pre-order for?
Answer
Anything where the root must come out first — copying a tree, serialising it to a file.
15. What is in-order for?
Answer
Sorted output. On a BST it always yields values in strictly ascending order.
16. What is post-order for, and why?
Answer
Anything where a parent needs results from both children before it can compute its own — directory sizes, expression evaluation, freeing memory in C. A node is visited only after everything beneath it.
C. Going iterative
17. Why bother writing the iterative versions at all? Two reasons.
Answer
- Recursion has a depth limit and an explicit stack does not. Python stops around 1,000 nested calls; a list holds millions. On a degenerate tree the recursive version crashes where the iterative one does not notice.
- Interviewers ask, because iterative in-order and post-order reveal whether you understand the traversal or memorised three lines.
18. Are the three iterative versions variations of one loop?
Answer
No. Pre-order is easy, in-order needs a different skeleton, post-order needs a trick. That unevenness is the honest shape of the topic.
19. Iterative pre-order: describe the loop.
Answer
Push the root. Repeatedly pop a node, visit it, push its children — right first, because a stack returns the last thing pushed, so pushing right first makes left come out first.
20. Why is iterative pre-order the easy one?
Answer
The node is visited the moment you first reach it, so there is nothing to remember. A node on the stack simply means “not started yet”.
21. Why can’t in-order use the same skeleton?
Answer
The node must not be visited when you first reach it — its whole left subtree has to come out first. So you cannot finish with a node on arrival.
22. Describe the iterative in-order loop.
Answer
A curr pointer drills all the way down the left edge, stacking nodes as it passes. When there is no more left, pop the most recent node, visit it, and turn right.
23. Why is the condition while curr or stack rather than while stack?
Answer
There are two separate ways for work to remain: you are holding a node you have not descended into (curr), or nodes are parked on the stack awaiting a visit. The traversal ends only when both are empty.
24. What does a node sitting on the in-order stack mean?
Answer
“I have gone past you on the way down, and I still owe you a visit.”
D. Post-order, the awkward one
25. Why is iterative post-order genuinely harder?
Answer
A node is visited only after both subtrees are done, so on arriving back at a node from below you must know which child you returned from. The stack alone does not tell you that.
26. Describe Option A (the reversal trick).
Answer
Run a modified pre-order that visits Root → Right → Left, then reverse the final list. Reversed, that is Left → Right → Root — post-order.
27. In Option A, which child is pushed first, and why is it the opposite of pre-order?
Answer
Left first, so right is popped first, giving Root → Right → Left on the way in. Plain pre-order pushes right first.
28. What is the serious catch in Option A?
Answer
It produces the right list in the wrong order of touching. The nodes are actually visited root-first (1, 3, 6, 2, 5, 4 on the lab tree); the reversal happens afterwards, to the list.
29. When is Option A fine and when is it wrong?
Answer
Fine when the work is collecting values. Wrong when the work is the visit — freeing memory, deleting nodes, closing files. You cannot reverse a free() that has already happened.
30. Describe Option B.
Answer
One stack plus a last_visited pointer. Drill left as in in-order; then peek at the top of the stack and ask whether its right subtree is already finished. If not, go right. If so, visit and pop.
31. What is the key line in Option B, and what question does it ask?
Answer
last_visited != peek_node.right — have I already finished this node’s right subtree?
32. How much of Option B is actually new?
Answer
Almost none. It reuses the in-order skeleton exactly — same while curr or stack, same drill-down-left. The only new idea is peeking instead of popping, and popping only once the node is genuinely finished.
E. Costs
33. Time complexity of all three traversals?
Answer
— every node is handled a constant number of times.
34. Space complexity, and in terms of what?
Answer
for the stack, where is the height — not , and not unless the tree is balanced.
35. Do the iterative versions use less memory than the recursive ones?
Answer
No — the same amount, in a place that is allowed to be much bigger. That is the entire benefit.
36. What is the worst-case space, and on what tree?
Answer
, on a degenerate tree where . That is exactly the case where the recursive version blows the call stack.
F. Recall drill
37. Given preorder = [1,2,4,5,3] and inorder = [4,2,5,1,3], reconstruct the tree.
Answer
Pre-order’s first element is the root: 1. Find 1 in in-order — everything left of it (4,2,5) is the left subtree, everything right (3) is the right. Recurse. You get the reference tree.
38. Why is pre-order + in-order enough to reconstruct a tree, but pre-order + post-order is not?
Answer
In-order is the only one that tells you where the split is — which nodes fall on each side of the root. Pre-order and post-order both identify the root but neither partitions the rest, so trees with single-child nodes become ambiguous.
39. Which traversal order would you use to delete a tree, and why?
Answer
Post-order, with a true post-order visit (Option B or recursion). You must free the children before the parent, because freeing the parent first loses the pointers to them.
40. Summarise the topic in one sentence.
Answer
Three orders are one algorithm with the visit line in three places — and going iterative just means writing down by hand the note the call stack was keeping for you.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Depth-First Traversals — the module
- Level-Order Traversal — Question Bank — the breadth-first counterpart
- Stacks and Queues — why one order needs a stack and the other a queue
Software engineering
Infrastructure & security
Computer science
Hardware & engineering