Binary Tree General

Reader guide and study workflow · Complete course map

Begin with what a parent needs to know

A node R has a leaf L on the left and a two-node chain M→N on the right. How many nodes are on the deepest root-to-leaf route? One baseline enumerates every route and counts it. But R does not need the routes themselves: it only needs the deepest length below each child, 1 and 2, then computes 1+max(1,2)=3. Returning zero for an empty child is forced by that meaning. The recursive function is a promise about one subtree before it is a traversal template.

Now ask whether two trees are the same. A single height is no longer enough: two equally tall trees can have different values or shapes. The state becomes a pair of nodes, with three distinct boundary cases: both absent, exactly one absent, and both present. For symmetry, keep the pair but change which children correspond. Recursion is useful here because the smaller question is precisely the original question with a smaller domain.

Let an impossible combination reveal missing state

Consider a root of value 4, with a left child 5 whose two children are 7 and 8, and a right child 6. The best path entirely through node 5 is 7→5→8, sum 20. Can the root add that entire result to itself and 6? No: attaching at 5 creates three incident path edges there, so the result is a fork rather than a path. A parent may extend only one downward arm. At 5 that arm has sum 5+max(7,8)=13, while the complete candidate remains 20. At root the legal complete candidate is 13+4+6=23.

This counterexample derives two roles: return an extendable gain; separately record complete paths. Naming both roles before coding prevents a locally plausible recurrence from combining incompatible objects. Negative child gains may be omitted, but an all-negative input still requires a real nonempty path.

Recover boundaries before consuming traversal data

Given preorder [8,3,5,12] and inorder [3,5,8,12], the first preorder item selects root 8; its inorder position tells us the left subtree has two nodes. Only then can we assign preorder [3,5] to that subtree and [12] to the right. A global traversal cursor and explicit subtree ranges are two valid representations, with different obligations. A backward postorder cursor consumes right before left; disjoint postorder ranges allow either recursion order. Unique values make the value→inorder-position map meaningful. Without that promise, selecting one occurrence requires more information.

Prerequisites and readiness

Know recursive calls, child pointers, preorder/inorder/postorder, and the difference between a return value and state accumulated across calls. Always define the meaning of a recursive result before combining children.

Reasoning workshop: write the recursive contract

A return value is a promise to the parent

MaxDepth returns a node count: nil contributes zero, and a real node returns one plus the larger child depth. SameTree returns equality of paired shapes and values, so exactly one nil child must fail. SymmetricTree pairs opposite child positions, not corresponding positions. These base cases come from the problem definition; “nil returns the neutral value” is not a universal rule that can be copied without thought.

Path Sum requires a leaf. A root 5 with a child 1 does not satisfy target 5, because stopping at the internal root is not allowed. Negative values also prevent pruning merely because a running sum has exceeded the target. Sum Root-to-Leaf Numbers carries a decimal prefix: root 1 with leaves 2 and 3 contributes 12+13=25, not the sum of node values.

Local gain and a complete path are different quantities

For Maximum Path Sum, imagine a node valued 10 with left gain 4 and right gain 7. A complete path through it can use both children and total 21. A branch offered to the parent can use only one child and total 17. Returning 21 upward would allow the parent plus both child branches, giving degree three at this node: that is not a simple path. Every legitimate path has a unique highest node, so recording a complete candidate there and returning only one extendable branch covers all possibilities. All-negative trees still require a nonempty answer, not zero.

Reconstruct from complementary traversal information

Preorder selects the root first; inorder locates its split. Build left before right while consuming preorder forward. Postorder selects the root last. A single cursor consuming it backward must build right before left. The supplied reference instead passes disjoint postorder and inorder ranges to each child, so it safely builds left before right. Child order depends on how traversal state is represented. For inorder [1,2,3], preorder [2,1,3] and postorder [1,3,2] both reconstruct root 2 with children 1 and 3. Unique values make the position map unambiguous. Keep traversal indices local to each call rather than relying on global state that survives into a second reconstruction.

Identity and ownership remain visible in trees

InvertTree swaps existing child edges and returns the original root. SameTree compares structure without mutation. LCA returns an existing pointer and assumes both distinct targets occur in the tree; equal values are not substitutes for identity. When one target is an ancestor of the other, that target is the answer. These are different contracts even though all functions recurse over TreeNode.

Bounds are not arithmetic guarantees

A bound of 100000 nodes does not make every decimal root-to-leaf number fit in int. SumNumbers therefore requires the total of all root-to-leaf numbers to fit the target int. Nonnegative digits make each path prefix at most its completed leaf number, and each subtree total at most the full total, so this answer guarantee also bounds the intermediate arithmetic. A deep path of nonzero digits can violate that guarantee even with only one leaf. Similarly, recursion uses O(h) stack, which becomes O(n) on a chain, not O(log n) for every tree.

Use independent serialized shape comparisons, root-to-leaf path enumeration, and all-pairs simple-path sums on small generated trees as oracles. Testing only balanced positive-valued trees leaves the hardest distinctions unexamined.

Reconstruction lab and answer key

Maximum Depth of Binary Tree

A root has a left leaf and a right chain of three nodes below the root. Predict the returned depth. How would the recurrence and empty-tree convention change if depth counted edges instead of nodes?

Model answer

The node-count depth is 4: the children return 1 and 3, and the root returns 1+max(1,3). For an edge-count definition with a leaf at 0, using nil depth −1 preserves the same 1+max recurrence; the empty tree then needs that explicitly chosen convention. A unit change requires revisiting base cases.

Same Tree

Tree A is root 2 with only left child 6. Tree B is root 2 with only right child 6. Both preorder value lists are [2,6]. Are they the same, and what information would serialization need to preserve?

Model answer

They are different because corresponding child positions differ. A preorder encoding needs nil markers (or equivalent shape information): [2,6,nil,nil,nil] differs from [2,nil,6,nil,nil]. Pairwise recursion detects the mismatch as soon as one corresponding child is nil and the other is not.

Invert Binary Tree

A root has left subtree L and right subtree R. Is it valid to invert L and R recursively before swapping them? What property should two consecutive inversions satisfy, including node identities?

Model answer

Yes. Invert each original subtree, then set Left to inverted R and Right to inverted L; saving the original children or computing both results before assignment avoids overwriting an unread reference. Inversion is an involution: twice restores every original Left/Right edge and value, with the same node objects.

Symmetric Tree

Two children of a root both have value 4. Each of those children has only a left child of value 7. Is the whole tree symmetric? State the node pair that disproves it.

Model answer

No. Mirror comparison pairs the left child’s Left (the 7 node) with the right child’s Right (nil). Equal values at the two children do not establish mirrored structure. The second pair is left.Right with right.Left, not matching same-side children.

Construct Binary Tree from Preorder and Inorder Traversal

Use preorder [14,8,5,11,20,17] and inorder [5,8,11,14,17,20]. Derive the root’s right-subtree ranges and its left child. What changes if values are no longer unique?

Model answer

Root 14 has three nodes to its left in inorder, so its right subtree receives preorder [20,17] and inorder [17,20]. That subtree is rooted at 20 with left child 17. Repeated values make a single value→position lookup ambiguous; the current unique-value contract is what permits this simple split.

Construct Binary Tree from Inorder and Postorder Traversal

For inorder [2,4,6,9] and postorder [2,6,4,9], what are the root and left subtree ranges? Could an explicit-range implementation build left first? Could a shared backward cursor?

Model answer

Root 9 is the last postorder item. Its left subtree uses inorder [2,4,6] and postorder [2,6,4], rooted at 4 with children 2 and 6; the right range is empty. Independent ranges allow left-first. A shared backward cursor must consume the right subtree before the left whenever both exist, because reversing postorder gives root, right, left.

Path Sum

A root 5 has only left child −2, which has only right child 4. Evaluate targets 5 and 7. Why is pruning as soon as a running sum exceeds the target unsafe?

Model answer

Target 5 is false because the root is not a leaf and the only full path sums to 7. Target 7 is true. Negative descendants can lower a running sum, so being temporarily above a target does not rule out a later match. Acceptance needs a real leaf and the full root-to-leaf sum.

Sum Root to Leaf Numbers

A root 2 has left leaf 0 and right child 3 with left leaf 4. Give the prefix state at node 3 and the two numbers being added. What does an absent child contribute?

Model answer

At node 3 the prefix becomes 10×2+3=23. The leaves contribute 20 and 234, so the total is 254. An absent child contributes 0 to the total; it is not a leaf that completes another number. Branches receive their own prefix values.

Binary Tree Maximum Path Sum

A tree has root −4 and leaf children −6 and −2. Give each leaf’s returned gain, the root’s returned gain, and the final answer. Which step would make a zero answer incorrect?

Model answer

The leaf gains are −6 and −2, and the best complete candidate among them is −2. At the root both negative child contributions are omitted, so its returned gain and candidate are −4. The final answer remains −2. Initializing the answer to 0 or treating an empty path as a candidate would violate the nonempty-path contract.

Lowest Common Ancestor of a Binary Tree

Suppose p is present but q is an unrelated allocated node outside the tree. What could the current recursion return? What extra information would support an API that must report missing targets?

Model answer

It can return p, because that is the only non-nil evidence found. That does not violate this exercise’s promise that both targets are present; it shows why the promise matters. A generalized API could return a candidate plus a count or two presence flags, then accept the candidate only when both distinct target pointers were found.

Problems in this module

• Maximum Depth of Binary Tree
• Same Tree
• Invert Binary Tree
• Symmetric Tree
• Construct Binary Tree from Preorder and Inorder Traversal
• Construct Binary Tree from Inorder and Postorder Traversal
• Path Sum
• Sum Root to Leaf Numbers
• Binary Tree Maximum Path Sum
• Lowest Common Ancestor of a Binary Tree

Interactive checkpoint

Open the Binary Tree General quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable