Algorithms from zero
Trees: multiple-choice review
Crux Multiple-choice synthesis across the trees unit — node structure, traversal choice, the BST invariant, balance and height, BFS vs DFS, and the tree-DP pattern.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skySix questions that cut across the whole unit. Each one is a decision you make when you reach for a tree in real code — not a definition to recite, but which traversal, which invariant, which complexity is actually in play.
Goal
Confirm you can connect node structure, traversal choice, the BST invariant, balance, BFS-vs-DFS, and the tree-DP pattern — the synthesis the individual lessons built toward.
Quiz
Completed
You must return the values of a binary search tree in ascending sorted order. Which single traversal does this directly, and why?
Heads-up The root of a BST is not the median — it is just the first value inserted. Pre-order emits the root before any left-subtree value, so the output is not sorted. Only in-order yields sorted order.
Heads-up Level-order groups nodes by depth, not by value. A node at depth 1 can be smaller or larger than a node at depth 2. BFS order has no relation to sorted order in a BST.
Heads-up The root is neither the minimum nor the maximum of a BST. Post-order emits both children before the node, so the sequence is not sorted.
Quiz
Completed
A teammate inserts the keys 1, 2, 3, 4, 5, 6, 7 into an empty BST in that exact order, then complains that search is slow. What happened, and what is the height?
Heads-up Height depends on insertion order, not just node count. Only a balanced shape gives height ~log n; sorted insertion produces a chain of height n-1.
Heads-up The invariant (left < node < right) holds perfectly — every node is larger than its parent. The tree is a valid BST; it is just degenerate, which is a balance problem, not an invariant violation.
Heads-up Search does not traverse the whole tree — it follows one root-to-target path. The slowness is the path length: in a height-6 chain that path is up to 7 nodes, i.e. O(n).
Quiz
Completed
You need every node grouped by its depth — all of level 0, then all of level 1, and so on. Which approach fits, and what is the key implementation detail?
Heads-up In-order is depth-first: it dives down the left spine before touching the right child, so nodes come out interleaved across levels. You would have to bucket by depth afterwards — BFS produces level groups directly.
Heads-up Visiting the root first does not give you level grouping. After the root, pre-order plunges into the entire left subtree (all depths) before seeing the right child. DFS cannot finish a level before going deeper.
Heads-up A plain BFS gives the correct visit order but not the level boundaries. Without snapshotting the size at each level start you cannot tell where one level ends and the next begins.
Quiz
Completed
In the standard recurse-and-combine pattern for trees, what does the base case return for an empty subtree when computing height (with the convention that a leaf has height 0)?
Heads-up Height counts edges, not nodes. If null returned 0, a leaf would compute 1 + max(0, 0) = 1, over-counting by one. Counting nodes is a different problem with a different base case.
Heads-up Returning null forces a special-case branch at every combine, which is exactly what the -1 (or 0-for-counts) numeric sentinel is designed to avoid. The point of the convention is uniform arithmetic.
Heads-up That double-counts. The whole purpose of choosing -1 for null is to make the leaf land at height 0 under the convention stated in the question.
Quiz
Completed
Computing the diameter of a binary tree (longest path between any two nodes), why does each recursive call return the subtree's height while the diameter is kept in a side variable?
Heads-up If a node returned the diameter, the parent could not extend it — a path through the parent uses one child's downward height, not the child's full diameter. The two quantities are different, which is exactly why the pattern splits them.
Heads-up Two passes (one for heights, one for diameter) traverses the tree twice and re-derives heights you already computed. The whole point of tree DP is one pass: return local info up, accumulate the global answer on the side.
Heads-up The longest path can lie entirely within a subtree and never touch the root. That is precisely why the maximum must be updated at every node, not just at the root.
Quiz
Completed
Two engineers compare an in-order recursive traversal and a level-order (BFS) traversal of the same balanced tree with n nodes. What is the dominant extra-space cost of each?
Heads-up Visiting n nodes is the time cost, not the space cost. Recursion holds only the current root-to-node path (O(h)); BFS holds only the current frontier (O(w)). Neither holds all n nodes at once in the general case.
Heads-up Recursion consumes the call stack — one frame per level on the active path, so O(h). On a degenerate (chain) tree that is O(n) and can overflow the stack.
Heads-up It is the reverse: DFS depth is bounded by the height h (stack), and BFS breadth is bounded by the widest level w (queue). On a balanced tree h ~ log n while w ~ n/2.
Recap
The through-line of the unit is one mapping: the shape of the data dictates the tool. A binary tree is a node with two subtrees, so recursion is the natural walk; the three DFS orders differ only in when the node is visited, and in-order is the one that reads a BST out sorted. The BST invariant buys O(h) search — but only balance keeps h near log n, and sorted-order insertion is the worst case that collapses it to O(n). BFS with a per-level size snapshot is the tool when depth matters, trading the stack for a queue. And tree DP returns local information up while accumulating the global answer on the side — one pass, two quantities.