Micro-questions over the tree traversal pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
This bank is about choosing an order. The mechanics are in the traversal bank.
A. What this note is for
1. What question does this pattern answer, as opposed to the traversal module?
Answer
Recognising when each order is the right tool — the mechanics of pre/in/post-order are elsewhere; choosing between them is the part that shows up as a decision.
2. Give the file-browser illustration of all three.
Answer
Preorder: list a directory before its contents. Postorder: compute a directory’s size after all subdirectory sizes. Inorder: list values in sorted order (BSTs only).
B. Preorder
3. When do you use it?
Answer
When you need to process or record a node before its children.
4. Give the canonical problem.
Answer
Building a root-to-leaf path string, since you need the ancestors already collected before you reach a leaf.
5. What exactly makes binary_tree_paths preorder?
Answer
path gets the current node appended before recursing into children — so by the time you reach a leaf, path already holds the full chain of ancestors.
6. What other operations are naturally preorder?
Answer
Copying a tree and serialising it, since the root must come first.
C. Postorder
7. When do you use it?
Answer
When a node’s answer depends on its children’s answers first.
8. Give the canonical problem.
Answer
Maximum path sum through a subtree — you need the best path from each child before combining at the parent.
9. In max path sum, why is max(dfs(node.left), 0) used?
Answer
To ignore negative contributions — a child path that loses value is better not taken at all.
10. Why does the function return something different from what it records?
Answer
It records node.val + left + right — a path that turns at this node — but returns node.val + max(left, right), because a path passing through to the parent can only use one side.
D. Inorder
11. When do you use it?
Answer
On a BST, when you need sorted output.
12. Why does inorder on a BST give sorted values?
Answer
The BST invariant says everything left of a node is smaller and everything right is larger — so visiting left, then node, then right emits values in ascending order by construction.
13. Does inorder give sorted output on any binary tree?
Answer
No — only on a BST. On an arbitrary binary tree it guarantees nothing.
E. Choosing
14. Give the four-row choice table.
Answer
Preorder — copying a tree, building a path string. Inorder — BSTs needing sorted output. Postorder — a node’s answer depends on its children’s. Level-order (BFS) — processing level by level.
15. State the deciding question in one line.
Answer
Does this node’s answer depend on what is above it (preorder), below it (postorder), or on its ordering (inorder)?
16. Summarise the pattern in one sentence.
Answer
Pick the order by where the information flows — down from ancestors, up from children, or across in sorted sequence.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Binary Tree Traversal Pattern — the pattern
- Depth-First Traversals — Question Bank — the mechanics
- DFS Pattern — Question Bank
Software engineering
Infrastructure & security
Computer science
Hardware & engineering