What may a parent extend?

Node 5 has children 7 and 8. Its parent 4 has another child 6.

The best path through 5 totals 20. May 4 attach that whole path to itself and 6?

1 / 12

Maximum Depth of Binary Tree — predict before coding

Depth counts nodes on a longest root-to-leaf path. The empty-tree base case zero makes a leaf's depth emerge naturally as one.

Decision: What are the depths of an empty tree, a leaf, and a four-node chain?

2 / 12

Same Tree — predict before coding

Value sequences alone omit shape. Equality must pair corresponding child positions, including nil positions.

Decision: Are a root 1 with left child 2 and a root 1 with right child 2 the same tree?

Presenter notes

Model answer: No. They contain the same values but place node 2 in different child positions.

Correctness argument: Two nil roots describe equal empty trees. Exactly one nil root describes different shapes. For two real roots, equality requires equal values and equality of their corresponding left subtrees and right subtrees. These conditions are necessary because any structural equality preserves each child position. They are sufficient because equal roots with equal corresponding subtrees can be combined into identical whole trees. Structural induction proves the recursive test. A mismatch can return early without changing either tree.

Debugging prompt: Compare serialization with explicit nil markers as an independent oracle. Tests using only preorder values can mistakenly consider different shapes equal.

3 / 12

Invert Binary Tree — predict before coding

Inversion is a structural permutation of existing child pointers, not a sort of values. The root node itself remains the same object.

Decision: After inverting a root with only a left child, where is that same child node?

Presenter notes

Model answer: It is the right child of the same root object. A freshly allocated equal-valued node would not preserve the mutation contract.

Correctness argument: An empty subtree remains empty. For a real node, exchange its left and right subtree roots, then invert each resulting subtree. By the inductive hypothesis, each child subtree is transformed into its mirror. Exchanging their positions and mirroring their interiors creates exactly the mirror of the entire original subtree. Every original node remains present once, with its value unchanged, and no new tree nodes are needed. Returning the original root pointer gives the caller access to the mutated tree.

Debugging prompt: Record every original node's left and right pointers, then verify they are exchanged after inversion. Double inversion is an additional check, not a substitute for checking one correct inversion.

4 / 12

Symmetric Tree — predict before coding

Mirror comparison pairs the outside children and the inside children. Comparing left with left tests equality, not symmetry.

Decision: Can equal values on the left and right roots prove symmetry when one has a left child and the other also has a left child?

Presenter notes

Model answer: No. Matching children must occur in mirrored positions: the left subtree's left child corresponds to the right subtree's right child.

Correctness argument: A pair of nil subtrees is mirrored; a pair with exactly one nil subtree is not. For two real subtree roots, their values must agree. The first root's left subtree must mirror the second root's right subtree, and its right must mirror the second's left. These are exactly the positions exchanged by reflection. Applying this condition recursively is necessary and sufficient by induction on the paired subtrees. Comparing the root's left and right children in this crossed manner therefore decides whole-tree symmetry. The empty tree is symmetric.

Debugging prompt: Use duplicate values with asymmetric missing-child positions. Equal value lists at each depth can still hide a structural asymmetry.

5 / 12

Construct Binary Tree from Preorder and Inorder Traversal — predict before coding

Preorder chooses the next root; inorder tells which values belong to each child subtree. Unique values make the split unambiguous.

Decision: For preorder [2,1,3] and inorder [1,2,3], which value is root and which inorder ranges belong to its children?

Presenter notes

Model answer: Root is 2. The left range contains [1], and the right range contains [3]. Preorder selects the root; inorder locates the split.

Correctness argument: For an empty inorder interval, return nil. Otherwise the next unused preorder value is the root because preorder visits root before either child. Its unique inorder position partitions the interval into exactly the left-subtree values and right-subtree values. Consume the root and recursively build the left interval before the right, matching preorder's consumption order. By induction, both subtrees are reconstructed correctly; attaching them gives the unique tree with those traversals. The inorder index map makes every split constant-time expected, and each preorder value is consumed once.

Debugging prompt: Use left chains, right chains, and irregular shapes. Verify both traversals and nil structure of the output. Keep traversal indices local to the call so repeated invocations do not share stale state.

6 / 12

Construct Binary Tree from Inorder and Postorder Traversal — predict before coding

Reading postorder through one backward cursor gives root, right, left, so that implementation builds right first. The reference instead gives each child its own ranges and safely builds left first.

Decision: For inorder [1,2,3] and postorder [1,3,2], which child subtree must be built first while consuming postorder backward?

Presenter notes

Model answer: The right subtree, rooted at 3. Backward postorder is 2,3,1: root, right, left.

Correctness argument: For a nonempty inorder interval, the last unused postorder value is its root because postorder visits both children before the root. The root's unique inorder position separates left and right values. After consuming that root backward, the next values belong to the right subtree, so reconstruct the right interval first and then the left. Induction on the interval size establishes that each call consumes exactly its subtree's values and reconstructs its correct shape. A map supplies each split without rescanning, and the backward index is exhausted exactly once across the tree.

Debugging prompt: A balanced three-node example exposes accidentally building left first. Also run two reconstructions sequentially to detect a non-reset global traversal index.

7 / 12

Path Sum — predict before coding

A root-to-leaf condition is stricter than reaching a target at any node. A zero remaining sum is meaningful only when the current node is a leaf.

Decision: For root 5 with a single child 1, is target 5 a successful root-to-leaf sum?

Presenter notes

Model answer: No. The root is not a leaf; the only root-to-leaf path sums to 6.

Correctness argument: At a recursive call, target is the amount still required from the current node through a leaf. An empty subtree supplies no root-to-leaf path and returns false, even if target is zero. At a leaf, the only possible path contains that node, so compare its value with target. At an internal node, every eligible path must continue into one of its actual child subtrees; subtract the current value and ask whether either child can supply the remainder. Induction over subtrees proves both that every accepted path ends at a leaf and that every eligible path is considered.

Debugging prompt: Test negative values, an empty tree with target zero, and a target achieved only at an internal node. With negatives, pruning because a partial sum exceeds target is unsound.

8 / 12

Sum Root to Leaf Numbers — predict before coding

The recursive state is the numeric value of the entire root-to-parent digit prefix. Extending by one digit is multiplication by ten plus that digit.

Decision: For root 1 with leaf children 2 and 3, why is the answer 25 rather than 6?

Presenter notes

Model answer: The paths spell 12 and 13, whose sum is 25. Node digits are concatenated along each path, not simply added.

Correctness argument: Assume prefix equals the number spelled by the path before the current node. Computing prefix*10+digit appends the current decimal digit and therefore gives the number for the extended path. At a leaf, this is one complete root-to-leaf number and is returned exactly once. At an internal node, complete paths partition into those entering the left child and those entering the right, so summing their results counts every path once without overlap. A nil subtree contributes zero. Structural induction proves the result whenever all arithmetic is representable in the retained int interface.

Debugging prompt: Test leading zero digits, one-sided trees, and several leaves sharing a long prefix. The published node-count bound alone does not ensure a 32-bit or 64-bit result.

9 / 12

Binary Tree Maximum Path Sum — predict before coding

A path may join two downward branches at one highest node, but a branch returned to a parent may use only one child. Mixing these two quantities creates a branching object rather than a path.

Decision: At a node valued 10 with child gains 4 and 7, what complete-path candidate is recorded and what gain can be returned to its parent?

Presenter notes

Model answer: Record 21 as the complete path through the node; return 17, using only the better child branch. Returning 21 upward could create three branches.

Correctness argument: For each node, let left and right be the best nonnegative gains extending down through one child. Any simple path whose highest node is the current one consists of the node plus at most one branch from each side, so node.Val+left+right is the best such complete path. Every tree path has exactly one highest node, so a global maximum over these candidates considers all paths. A path that will continue to the parent cannot take both child branches, because adding the parent would give degree three at the current node. Return node.Val+max(left,right) as the extendable gain. Initializing the global answer below all node values preserves a nonempty answer for all-negative trees.

Debugging prompt: Test all-negative nodes and a best path wholly inside a subtree. The path need not contain the root. A nonempty path may move up to one ancestor and then down another branch.

10 / 12

Lowest Common Ancestor of a Binary Tree — predict before coding

The return value summarizes whether the subtree contains a target or already contains their common ancestor. Target identity is a pointer relation, not a value comparison.

Decision: If p is an ancestor of q, should the answer be p or p’s parent?

Presenter notes

Model answer: p itself. A node is included in its own subtree, so it can be the lowest common ancestor of itself and a descendant.

Correctness argument: If the current root is nil, it contains neither target. If it is p or q, return that node: because both targets are guaranteed to exist in the original tree, it is a valid ancestor candidate even when the other lies below it. Otherwise recurse into both children. Non-nil results from both sides mean the targets split across the two child subtrees, making the current node their lowest common ancestor. A result from only one side contains all target evidence found here, so propagate it unchanged. No deeper node can be common when the targets split, and propagation preserves an already deeper candidate, proving lowestness.

Debugging prompt: Use equal-valued distinct nodes and targets where one is an ancestor of the other. Both p and q are distinct pointers present in the tree; the reference is not a general missing-target validator.

11 / 12

Change the return contract

The LCA helper assumes both target pointers are present. A new API must return nil if either is missing.

Construct a failing input for the old helper, then specify enough returned information to repair the promise.

12 / 12