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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to LeetCode Patterns — University-Style Teaching Notes