Tree Problem Patterns
Most binary-tree problems are one of two recursions. Either information flows down — each node receives something from its parent (the path so far, the maximum so far, a depth, a column) and the answer is assembled at the nodes it reaches — or information flows up — each node asks its children for a summary of their subtrees (a height, a sum, a "found it" pointer) and combines the summaries into its own. The first is the top-down template; the second is the bottom-up template. Knowing which one a problem needs, and what exactly each call should receive or return, is most of the work.
This lesson builds both templates from first principles, then runs through the canonical problems: depth and height, the balanced check, diameter with a proof, maximum path sum, path sums I, II and III (the last with prefix sums on root-to-node paths), lowest common ancestor with a proof, the four views, invert, symmetric, subtree check (naive versus serialization and hashing), flatten to a linked list, count good nodes, distribute coins, and a preview of tree dynamic programming through House Robber III. It assumes Binary Trees & Traversals: traversal orders, the level-order builder and the recursion-depth caveats are not repeated here.
Why this exists
Tree questions are the largest single family in technical interviews, and the reason is not that trees are common in day-to-day code. It is that a tree problem is the purest test of whether someone can write a recursive function whose contract — what it receives, what it returns, what it may assume about its recursive calls — is precise. A vague contract produces code that works on the three-node example and fails on a skewed tree, a tree of negative values, or a tree where the answer does not pass through the root.
The two-template view is old. Donald Knuth formalised it in 1968 as attribute grammars: in a parse tree, inherited attributes flow from parent to children and synthesized attributes flow from children to parent. Every compiler since has used that split — the scope a variable is looked up in is inherited (top-down), the type of an expression is synthesized (bottom-up). User-interface layout engines use the same pair; Flutter's documentation summarises its layout protocol as "constraints go down, sizes go up, parent sets position". The interview problems on this page are those same two flows on small trees.
The second reason the patterns matter is efficiency. The naive way to solve a tree problem — compute some quantity separately at every node, each time with a fresh traversal — is on a skewed tree. The patterns here all have the same shape: one traversal, work per node, total. Getting from the naive version to that shape is always the same move: make the recursion return more (a tuple instead of a number) or receive more (an accumulator), so that no subtree is ever traversed twice.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "from the root", "path from root to", "ancestors", "so far along the path", "depth of each node" | Top-down: pass the state as a parameter |
| "height", "size of subtree", "is balanced", "sum of subtree", anything a node can compute from its children's answers | Bottom-up: return the summary |
| "longest path between any two nodes", "diameter" | Bottom-up height, update a global with left + right |
| "maximum path sum", path can start and end anywhere | Bottom-up "best downward gain", global "best through this node" |
| "root-to-leaf path with sum", "all such paths" | Top-down remaining sum (+ backtracking list for II) |
| "number of downward paths with sum ", start anywhere | Prefix sums on the root-to-node path + hash map (Path Sum III) |
| "lowest common ancestor", "first shared ancestor" | Bottom-up "return the node if found" |
| "visible from the right / left / top / bottom" | Level order (left/right) or column tracking (top/bottom) |
| "mirror", "invert", "symmetric" | Simultaneous recursion on two subtrees |
| "is one tree a subtree of another", "duplicate subtrees" | Serialization or subtree hashing / interning |
| "flatten in preorder", "in place" | Reverse-postorder with prev, or the Morris-style rewiring |
| "count nodes where something holds relative to ancestors" | Top-down with the relevant ancestor statistic |
| "moves along edges to balance a quantity" | Bottom-up excess; each edge carries |
| "choose nodes, no two adjacent" | Bottom-up pair (take, skip) — tree DP |
Intuition & first principles
The contract is everything
Write every tree function as: given a node (possibly null) and some arguments, return something about that node's subtree. Then three things must be pinned down before a line of code:
- What does a call receive? Only the node (pure bottom-up), or the node plus state from above (top-down)?
- What does a call return? A number, a boolean, a node, a tuple?
- What does the null case return? This is where half the bugs live. Height of null is if you count edges (0 if you count nodes); sum of null is 0; "found" in null is null; maximum gain of null is 0, not , when you are allowed to stop a path early.
Then the body is induction. Assume the recursive calls satisfy the contract on the children (the induction hypothesis — Recursion & Mathematical Induction is the formal version) and show that the combination satisfies it for the node.
Top-down: pass state down
# fragment — top-down template
def solve(root):
answer = initial
def dfs(node, state): # state: what the path from the root has told us
nonlocal answer
if node is None:
return
state2 = update(state, node) # include this node
if is_leaf(node): # or at every node
answer = combine(answer, state2)
dfs(node.left, state2)
dfs(node.right, state2)
dfs(root, start_state)
return answer
The node sees everything about its ancestors that the state encodes, and nothing about its descendants. Use it when the property at a node depends on the path above it: "is this node at least as large as every ancestor?" (good nodes), "does the root-to-here sum equal the target at a leaf?" (path sum), "what depth / column am I at?" (views, vertical order). It is preorder in spirit: the node does its work before its children.
Bottom-up: return values up
# fragment — bottom-up template
def solve(root):
def dfs(node): # returns: summary of node's subtree
if node is None:
return base_summary
left = dfs(node.left)
right = dfs(node.right)
return combine(node, left, right)
return finish(dfs(root))
The node sees everything its children's summaries encode, and nothing about its ancestors. Use it when the property at a node depends on the subtree below it: height, size, sum, balance, "does this subtree contain ?". It is postorder: children first.
Bottom-up with a side channel
Many of the famous problems need two different quantities at each node: one that can be extended upward by the parent (a downward path from this node) and one that is final at this node (a path that bends here and cannot be extended). Diameter and maximum path sum are the canonical examples. The template returns the extendable quantity and records the final one in an outer variable (or returns both in a tuple):
flowchart TD
subgraph TD1["top-down: state flows to children"]
A1["root<br/>state = s0"] -->|"s1 = f(s0, root)"| B1["child"]
A1 -->|"s1"| C1["child"]
B1 -->|"s2 = f(s1, child)"| D1["grandchild"]
end
subgraph BU1["bottom-up: summaries flow to parent"]
D2["grandchild"] -->|"returns g(...)"| B2["child"]
C2["child"] -->|"returns g(...)"| A2["root<br/>combine(left, right)"]
B2 -->|"returns g(...)"| A2
end
The choice is not always forced. Maximum depth can be computed top-down (pass depth, record the maximum at leaves) or bottom-up (return of children). When both work, bottom-up usually needs no outer variable and composes better; top-down is natural when the answer is attached to leaves or to paths from the root.
Returning more than one value
The fix for almost every tree solution is "return a tuple". Each language has an idiom:
- Python: return a tuple and unpack it,
h, ok = dfs(node.left); for more than two fields aNamedTupleor@dataclass(slots=True)documents the meaning. Anonlocalvariable in a nested function is the usual side channel. - Java: a
record(Java 16+) is a one-line immutable tuple with named fields:record Info(int height, boolean balanced) {}. Records can be declared locally inside a method. For a side channel, use an instance field or a one-element array (int[] best = {0}), since lambdas and inner classes cannot assign captured locals. - C++: a small
structreturned by value, unpacked with structured bindings,auto [h, ok] = dfs(node->left);. Return value optimisation makes it free.std::pairworks but.first/.secondhide meaning. A side channel is a reference parameter or a member of a solver struct. - TypeScript: return a tuple type
[number, boolean]and destructure,const [h, ok] = dfs(node.left);, or an object{ height, balanced }. A closure variable is the side channel.
The Implementation section uses all four idioms.
Mechanics
The running example for this section is the tree built from [1, 2, 3, 4, 5, null, null, 6, null, null, 7, 8, null, null, 9]:
flowchart TD
n1((1)) --> n2((2))
n1 --> n3((3))
n2 --> n4((4))
n2 --> n5((5))
n4 --> n6((6))
n5 --> n7((7))
n6 --> n8((8))
n7 --> n9((9))
style n8 stroke-width:3px
style n6 stroke-width:3px
style n4 stroke-width:3px
style n2 stroke-width:3px
style n5 stroke-width:3px
style n7 stroke-width:3px
style n9 stroke-width:3px
The bold nodes form its longest path, 8–6–4–2–5–7–9: 6 edges, and it does not pass through the root.
Depth and height
Height bottom-up: , . The example has height 4 (root to 8 or to 9). LeetCode's "maximum depth" counts nodes, giving 5; the code is the same with for null. Minimum depth (nearest leaf) is a classic trap: is wrong when one child is null, because a null child is not a leaf. Take the minimum only over existing children, or use BFS and stop at the first leaf, which is faster on wide shallow-leaf trees.
Balanced check in O(n)
A tree is height-balanced if at every node . The direct transcription — check the root's subtrees' heights, then recurse into both subtrees — recomputes heights from scratch at every node. Each node's height is computed once per ancestor, so the cost is the sum of depths: on a balanced tree and on a path if the checks do not short-circuit.
The bottom-up version returns the height and the verdict together. A compact encoding uses a sentinel: return (any impossible height) to mean "unbalanced somewhere below", and propagate it immediately.
# fragment — balanced check with a sentinel
def height_or_fail(node) -> int: # returns height, or -2 if unbalanced
if node is None:
return -1
l = height_or_fail(node.left)
if l == -2: return -2
r = height_or_fail(node.right)
if r == -2 or abs(l - r) > 1: return -2
return 1 + max(l, r)
Each node is visited once: time, stack. The early exit also means an imbalance deep in the left subtree stops the traversal before the right subtree is touched.
Diameter
The diameter is the number of edges on the longest path between any two nodes. Every path in a tree has a unique highest node (the one closest to the root), and the path consists of a downward path into that node's left subtree and one into its right subtree. The longest downward path from into its left subtree has edges, so the longest path whose highest node is has edges (with this correctly gives 0 for a leaf and for a one-sided node). The diameter is the maximum of that over all , computed in the same postorder pass that computes heights.
Here is the pass traced by hand on the example, one row per node in the order postorder finishes them. through is ; best is the running maximum. The table was produced by running the algorithm.
| Node | returned | through | best so far | ||
|---|---|---|---|---|---|
| 8 | −1 | −1 | 0 | 0 | 0 |
| 6 | 0 | −1 | 1 | 1 | 1 |
| 4 | 1 | −1 | 2 | 2 | 2 |
| 9 | −1 | −1 | 0 | 0 | 2 |
| 7 | −1 | 0 | 1 | 1 | 2 |
| 5 | −1 | 1 | 2 | 2 | 2 |
| 2 | 2 | 2 | 3 | 6 | 6 |
| 3 | −1 | −1 | 0 | 0 | 6 |
| 1 | 3 | 0 | 4 | 5 | 6 |
The root's "through" value is 5, so an answer of at the root alone would be wrong; the maximum, 6, occurs at node 2. A brute-force check (BFS from every node, take the farthest distance) agrees.
Maximum path sum
Now nodes carry values, possibly negative, and a path is any sequence of nodes connected by edges with no repeats, containing at least one node. Maximise the sum of values.
Define as the best sum of a downward path that starts at — the extendable quantity:
The says a path may stop at rather than continue into a subtree whose best contribution is negative. The best path whose highest node is — the final quantity — is
Return gain, track the best "through" value globally, initialised to (not 0: a tree of all-negative values has a negative answer, the largest single value). On the tree [-3, 9, 20, null, null, 15, -7] the answer is : the negative root is worth including because it connects two large positive branches. On the single node [-5] the answer is .
Path sum I and II: top-down remaining sum
Path Sum I: is there a root-to-leaf path whose values add up to a target? Pass the remaining target down; at a leaf, check whether the remainder equals the leaf's value. Path Sum II: list all such paths. Keep a single path list, append on entry, pop on exit (backtracking), and copy it into the answer at a matching leaf. The copy is what makes II in the worst case rather than : up to leaves can each produce an path.
On the tree [1, -2, 3, 4, 1, null, -1, null, null, 2] with target 3, the root-to-leaf paths are 1→−2→4 (sum 3), 1→−2→1→2 (sum 2) and 1→3→−1 (sum 3), so Path Sum II returns [[1, -2, 4], [1, 3, -1]]. Negative values are why you cannot prune when the running sum exceeds the target.
Path sum III: prefix sums on the root-to-node path
Path Sum III counts downward paths (any start node, any end node below it on the same branch) whose sum equals the target. The naive approach starts a path-sum DFS from every node: , which is on a path.
The fix is the subarray-sum trick from Prefix Sums & Difference Arrays, applied to the root-to-current-node path, which is an array that grows and shrinks as the DFS moves. Let be the sum of values from the root down to . A downward path from to ( an ancestor of , inclusive) has sum . So the number of good paths ending at equals the number of ancestors-or-root-sentinel with . Keep a hash map freq of prefix sums on the current path, seeded with {0: 1} for the empty prefix above the root. At each node: compute , add freq[S(v) - target] to the count, increment freq[S(v)], recurse into both children, then decrement freq[S(v)] on the way out so that the map describes only the current path.
The run on the same tree with target 3, produced by script (the map is shown before this node's prefix is added):
| Node | Path | Need | freq[need] | Count | freq on path | |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | −2 | 0 | 0 | {0:1} |
| −2 | 1, −2 | −1 | −4 | 0 | 0 | {0:1, 1:1} |
| 4 | 1, −2, 4 | 3 | 0 | 1 | 1 | {0:1, 1:1, −1:1} |
| 1 | 1, −2, 1 | 0 | −3 | 0 | 1 | {0:1, 1:1, −1:1} |
| 2 | 1, −2, 1, 2 | 2 | −1 | 1 | 2 | {0:2, 1:1, −1:1} |
| 3 | 1, 3 | 4 | 1 | 1 | 3 | {0:1, 1:1} |
| −1 | 1, 3, −1 | 3 | 0 | 1 | 4 | {0:1, 1:1, 4:1} |
The four paths are 1→−2→4, 1→2 (the lower 1), 3 alone, and 1→3→−1. Note row 6: when the DFS moves from the left subtree to node 3, the entries for −1, 0 and 2 have been removed — without the decrement, paths would be counted that jump between branches. time, space for the map and the stack.
Lowest common ancestor
The lowest common ancestor (LCA) of nodes and is the deepest node that has both as descendants (a node counts as its own descendant). In the example, , and .
The bottom-up recursion returns, for each subtree, "a node of interest found in it": or if the subtree contains exactly one of them, the LCA if it contains both, null if neither.
# fragment — LCA, assuming p and q are both in the tree
def lca(node, p, q):
if node is None or node is p or node is q:
return node
left = lca(node.left, p, q)
right = lca(node.right, p, q)
if left and right: # p and q are on different sides: node is the split point
return node
return left or right # both on one side (that side's answer), or neither (null)
flowchart TD
S{"node is null, p or q?"} -->|"yes"| R1["return node"]
S -->|"no"| B["recurse left and right"]
B --> C{"both non-null?"}
C -->|"yes"| R2["return node: this is the LCA"]
C -->|"no"| R3["return whichever is non-null, or null"]
The proof is in the Correctness section; it relies on both nodes being present. If one may be missing, either check presence first or have the recursion return a count of targets found alongside the node. In a BST the LCA is simpler (walk down from the root until and fall on different sides), and for many LCA queries on a fixed tree, binary lifting or an Euler tour answers each in or — see LCA, Binary Lifting & Euler Tour.
Views: left, right, top, bottom
- Right view: the last node of each level. BFS with the level-size snapshot, or DFS visiting right before left and recording a node whenever its depth equals the number of nodes recorded so far (the first node seen at each new depth). The example's right view is 1, 3, 5, 7, 9.
- Left view: the first node of each level — 1, 2, 4, 6, 8.
- Top view: for each column (root 0, left −1, right +1), the first node BFS reaches. Using BFS, not DFS, matters: DFS can reach a deeper node in a column before a shallower one.
- Bottom view: for each column, the last node BFS reaches (overwrite as you go). On ties at the same depth, the conventional answer is the later one in BFS order.
from collections import deque
class T:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def top_and_bottom_views(root):
top, bottom, q = {}, {}, deque([(root, 0)] if root else [])
while q:
node, col = q.popleft()
top.setdefault(col, node.val) # first reached in BFS = topmost
bottom[col] = node.val # last reached = bottommost
if node.left: q.append((node.left, col - 1))
if node.right: q.append((node.right, col + 1))
cols = sorted(top)
return [top[c] for c in cols], [bottom[c] for c in cols]
ex = T(1, T(2, T(4, T(6, T(8))), T(5, None, T(7, None, T(9)))), T(3))
assert top_and_bottom_views(ex) == ([8, 6, 4, 2, 1, 3, 9], [8, 6, 4, 2, 5, 7, 9])
assert top_and_bottom_views(None) == ([], [])
In the example, column 0 holds 1 (depth 0) and 5 (depth 2), so the top view shows 1 and the bottom view shows 5; column 1 holds 3 and 7.
Invert and symmetric
Invert (mirror) a tree: swap every node's children. Any traversal works — preorder, postorder or BFS — because each swap is local; inorder is the one trap, since after swapping at a node, "go right" revisits the subtree you just processed. The inverted tree's inorder is the reverse of the original's.
Symmetric: a tree is a mirror of itself iff its left and right subtrees mirror each other. Recurse on pairs: mirror(a, b) holds iff both are null, or both exist with equal values and mirror(a.left, b.right) and mirror(a.right, b.left). The same two-pointer recursion decides "same tree" with the children paired straight instead of crossed. Iteratively, push pairs onto a queue.
Subtree check: naive versus serialization versus hashing
Is tree (size ) identical to some subtree of (size )?
Naive. At every node of , run a same-tree comparison against . A comparison stops at the first mismatch but can cost , so the worst case is — a tree of all-equal values that differ only in one deep leaf triggers it.
Serialization. Serialize both with preorder and null markers (the unique encoding from the previous lesson), with a separator before every token so that 2 cannot match inside 12: ,1,,2,#,#,#. Then is a subtree of iff is a substring of . Proof sketch: the serialization of a subtree is a contiguous block of the parent's serialization (preorder writes a subtree contiguously), and conversely a substring that is a complete encoding and starts at a token boundary must be the encoding of the subtree rooted at that token — by the prefix-free lemma. With a linear-time string matcher (KMP or Z-function, Module 7) the whole check is . Beware that library contains/find methods may be worst-case quadratic: CPython's in has used a linear-time two-way algorithm for long needles since 3.10, but Java's String.contains and typical std::string::find are naive in the worst case.
Hashing / interning. Compute an identifier for every subtree bottom-up from (value, id(left), id(right)). With a Merkle-style hash (hash of the triple) the ids are compact but can collide, so confirm a match with a real comparison. With interning — a hash map from the triple to a fresh integer id, shared between both trees — equal ids mean identical subtrees exactly, with no false positives, in expected . Interning (also called hash-consing) also finds all duplicate subtrees in one pass (LeetCode 652).
class T:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def is_subtree_interned(s, t) -> bool:
ids: dict[tuple, int] = {}
def intern(node) -> int: # 0 is the id of the empty tree
if node is None:
return 0
key = (node.val, intern(node.left), intern(node.right))
if key not in ids:
ids[key] = len(ids) + 1
return ids[key]
seen: set[int] = set()
def collect(node) -> int:
if node is None:
return 0
key = (node.val, collect(node.left), collect(node.right))
i = ids.setdefault(key, len(ids) + 1)
seen.add(i)
return i
target = intern(t)
collect(s)
return t is None or target in seen
s = T(1, T(2, T(4, T(6, T(8))), T(5, None, T(7, None, T(9)))), T(3))
assert is_subtree_interned(s, T(5, None, T(7, None, T(9))))
assert not is_subtree_interned(s, T(5, None, T(7))) # same values, missing leaf
assert is_subtree_interned(s, T(3))
Flatten to a linked list
Rewire the tree in place so that following right pointers visits the nodes in preorder and every left is null. Two approaches:
- Reverse postorder with
prev. Visit right subtree, then left subtree, then the node (the reverse of preorder), keepingprev= the node processed last. At each node setnode.right = prev,node.left = null,prev = node. Because nodes are processed in reverse preorder, each node is linked to its preorder successor. stack. - Morris-style rewiring, space. At
curwith a left subtree, find the rightmost node of the left subtree (the last node of the left subtree in preorder), attachcur.rightto it, move the left subtree to the right, null outleft, and continue withcur.right. The same edge-disjoint-spines argument as Morris traversal bounds the total work by .
On the example, the flattened list is 1, 2, 4, 6, 8, 5, 7, 9, 3 — the preorder.
Count good nodes
A node is good if no node on the path from the root to it has a larger value. Top-down: pass max_so_far; a node is good iff node.val >= max_so_far; recurse with max(max_so_far, node.val). On [2, 1, 5, 3, null, 2, 6] the good nodes are 2, 5, 3 and 6 — four. (3 is good because its path is 2 → 1 → 3.) It cannot be bottom-up: whether a node is good depends only on its ancestors.
Distribute coins
Each node holds some coins, the total equals the number of nodes, and a move transfers one coin across one edge. Minimise moves so every node has exactly one coin. Bottom-up: let , the number of coins the subtree of must send to its parent (negative means it must receive). Every coin that crosses the edge between and its parent counts once, so the answer is . On [0, 0, 0, 3, 0, 0, 4] the answer is 8. The proof is a cut argument: the edge above separates its subtree from the rest, so at least coins must cross it, and moving coins greedily toward deficits achieves exactly that on every edge simultaneously.
House Robber III: a preview of tree DP
Choose a set of nodes, no two of which are parent and child, maximising the total value (a maximum-weight independent set on a tree). A single number per subtree is not enough — the parent needs to know whether the child was taken. Return a pair:
On [4, 1, 5, 2, null, 1, 3] the root returns (take, skip) = (10, 7), so the answer is 10 (take 4, 2, 1 and 3). This "return a small vector of states per subtree" is tree dynamic programming, developed fully in Module 6 (Tree DP & Rerooting), where it handles independent sets, vertex covers, and answers for every possible root at once.
The ladder: brute force → better → optimal
Three problems show the same move from quadratic to linear.
Balanced check. Brute force: at each node compute both subtree heights with separate traversals and recurse — on balanced trees, on a path without short-circuiting. Optimal: one postorder pass returning height-or-sentinel — . Why it improves: each height is computed once and reused by the parent instead of recomputed by every ancestor.
Diameter. Brute force: BFS from every node and take the largest distance — . Better: at each node, call a separate height on both children — on a path, balanced. Optimal: heights in one postorder pass with a side channel for the best through-value — . (A second linear method: BFS from any node to the farthest node , then BFS from ; the farthest distance from is the diameter. It works on any tree, including unrooted ones, and is the standard for general trees in Graphs.)
Path Sum III. Brute force: from every node, a DFS counting downward paths — , i.e. on a path. Optimal: prefix sums on the root-to-node path with a backtracked hash map — expected. Why: the count of paths ending at becomes one hash lookup instead of a walk over 's ancestors.
| Problem | Brute force | Optimal | What changed |
|---|---|---|---|
| Balanced | worst | return height and verdict together | |
| Diameter | return height, record left + right + 2 | ||
| Max path sum | (try every pair or every top node with fresh traversals) | return best downward gain, record best bend | |
| Path Sum III | prefix-sum hash map on the current path | ||
| Subtree check | serialization + linear matcher, or interning | ||
| Flatten | extra list | extra | Morris-style rewiring |
Correctness
Diameter
Claim. The diameter equals with .
Proof. () For each , concatenating a longest downward path into the left subtree, , and a longest downward path into the right subtree gives a path of exactly edges (if a side is empty, its contribution ). So the diameter is at least every term. () Take any longest path . Its nodes have a unique node of minimum depth: if two nodes of minimum depth were on , the path between them would have to go up through their common ancestor, which is shallower, a contradiction. From , descends into at most one child subtree on each side, so consists of a downward path into 's left subtree (at most edges counting the edge from ) and one into the right subtree (at most ). So for that .
The algorithm computes every term exactly once in postorder and keeps the maximum, so it is correct and .
Maximum path sum
Same structure. Induction shows is the maximum sum of a downward path starting at : such a path is alone or followed by a downward path starting at a child, and the best of those is of that child; chooses "stop here" when both children's gains are negative. Every path has a unique highest node and is plus at most one downward path into each child subtree, each of which contributes at most ; and that bound is achieved. So the maximum over of the through-value is the answer. Initialising the global to (or to the root's value) matters because the through-value of every node may be negative.
Lowest common ancestor
Assume and are distinct nodes both present in the tree (the case also works, returning ). Define the contract of lca(node):
- if the subtree of
nodecontains both and , return their LCA; - if it contains exactly one of them, return that one;
- if it contains neither, return null.
Proof by induction on subtree size. Null contains neither: returns null. ✓. If node is (or ), the function returns node without recursing. If the subtree contains only , that is correct. If it also contains , then is a descendant of , so itself is the LCA — also correct. Otherwise node is neither. By the induction hypothesis, left and right satisfy the contract on the children. If both are non-null, each child subtree contains exactly one target (it cannot contain both, or the other side would contain neither and return null), so node is the deepest node above both — the LCA. If exactly one is non-null, all targets in the subtree are on that side and that side's return value is already correct for this subtree. If both are null, neither target is here.
The contract shows why presence matters: if is absent, the function returns for the whole tree, indistinguishable from " is the LCA of and its descendant ".
Path Sum III
Invariant. When the DFS enters node , freq holds exactly the multiset — the prefix sums of the current path above , plus the empty prefix. The decrement on exit restores the map to what it was on entry, so when control passes to a sibling or back to the parent, the invariant holds for the next node. A downward path ending at starts at some node on the root-to- path and has sum (with ). It equals the target iff , and the number of such is exactly freq[S(v) - target] by the invariant. Summing over all counts every good path once, by its lower endpoint.
Balanced check and distribute coins
The sentinel version satisfies: "returns iff some node in the subtree violates balance; otherwise returns the height". Induction is immediate — a subtree is balanced iff both child subtrees are and the root's heights differ by at most one. For distribute coins, the lower bound is the cut argument above; the upper bound holds because a schedule that, edge by edge from the leaves up, ships surpluses toward the parent and deficits from the parent never moves a coin across an edge more than times in total, and at the end every node has one coin since the total equals .
Complexity
| Problem | Time | Extra space | Notes |
|---|---|---|---|
| Height / max depth | |||
| Min depth | , BFS can stop early | BFS, DFS | BFS returns at the first leaf |
| Balanced (sentinel) | early exit on first imbalance | ||
| Diameter, max path sum | one postorder pass | ||
| Path Sum I | |||
| Path Sum II | worst | + output | copying paths dominates |
| Path Sum III | expected | hash map holds only the current path | |
| LCA (single query) | many queries: see binary lifting | ||
| Right / left view | or | BFS or DFS | |
| Top / bottom view | with an offset array, with sorted columns | ||
| Invert, symmetric, same tree | |||
| Subtree: naive / serialized / interned | / / expected | / / | |
| Flatten | or | Morris-style for | |
| Good nodes, distribute coins, House Robber III |
Where is the height () and the maximum width. All bounds are worst-case except the hash-map ones, which are expected. Recursion depth equals , so every recursive solution here has the overflow caveat on skewed trees from the previous lesson; each can be made iterative with the visited-flag template, at the price of keeping the per-node summaries in a map or on the explicit stack.
A note on constants: these algorithms touch each node once with a handful of arithmetic operations, so their run time is dominated by pointer chasing. Returning a small struct or tuple costs essentially nothing in C++ and Java (scalar replacement by the JIT often eliminates record allocation in hot code, though that is an optimisation, not a guarantee); in Python, tuple creation is measurable but rarely the bottleneck compared with the interpreter's per-call overhead.
Implementation
Two self-checking code groups. The first is the bottom-up toolkit — height, balanced, diameter, maximum path sum, LCA, distribute coins and House Robber III — showing tuple returns in each language. The second is the top-down and structural toolkit — good nodes, path sums I to III, views, invert, symmetric, subtree check and flatten. All trees are built from level-order arrays with nulls and all four languages assert the same answers.
from collections import deque
from typing import NamedTuple
class TreeNode:
def __init__(self, val: int):
self.val = val
self.left: "TreeNode | None" = None
self.right: "TreeNode | None" = None
def build(level: list[int | None]) -> TreeNode | None:
if not level or level[0] is None:
return None
root = TreeNode(level[0])
q, i = deque([root]), 1
while q and i < len(level):
node = q.popleft()
if i < len(level) and level[i] is not None:
node.left = TreeNode(level[i]); q.append(node.left)
i += 1
if i < len(level) and level[i] is not None:
node.right = TreeNode(level[i]); q.append(node.right)
i += 1
return root
def find(root, val):
if root is None or root.val == val:
return root
return find(root.left, val) or find(root.right, val)
def height(node) -> int: # edges; null = -1
return -1 if node is None else 1 + max(height(node.left), height(node.right))
def is_balanced(root) -> bool:
def go(node) -> int: # height, or -2 if unbalanced below
if node is None:
return -1
l = go(node.left)
if l == -2:
return -2
r = go(node.right)
if r == -2 or abs(l - r) > 1:
return -2
return 1 + max(l, r)
return go(root) != -2
class Info(NamedTuple): # tuple return: height and best path inside
height: int
diameter: int
def diameter(root) -> int:
def go(node) -> Info:
if node is None:
return Info(-1, 0)
a, b = go(node.left), go(node.right)
through = a.height + b.height + 2
return Info(1 + max(a.height, b.height), max(a.diameter, b.diameter, through))
return go(root).diameter
def max_path_sum(root) -> int:
best = float("-inf")
def gain(node) -> int: # side channel: nonlocal best
nonlocal best
if node is None:
return 0
l, r = max(0, gain(node.left)), max(0, gain(node.right))
best = max(best, node.val + l + r)
return node.val + max(l, r)
gain(root)
return best
def lca(node, p, q):
if node is None or node is p or node is q:
return node
left, right = lca(node.left, p, q), lca(node.right, p, q)
if left and right:
return node
return left or right
def distribute_coins(root) -> int:
moves = 0
def excess(node) -> int:
nonlocal moves
if node is None:
return 0
l, r = excess(node.left), excess(node.right)
moves += abs(l) + abs(r)
return node.val - 1 + l + r
excess(root)
return moves
def rob(root) -> int:
def go(node) -> tuple[int, int]: # (take, skip)
if node is None:
return 0, 0
lt, ls = go(node.left)
rt, rs = go(node.right)
return node.val + ls + rs, max(lt, ls) + max(rt, rs)
return max(go(root))
if __name__ == "__main__":
t = build([1, 2, 3, 4, 5, None, None, 6, None, None, 7, 8, None, None, 9])
assert height(t) == 4 and not is_balanced(t) and diameter(t) == 6
assert lca(t, find(t, 8), find(t, 9)).val == 2
assert lca(t, find(t, 8), find(t, 3)).val == 1
assert lca(t, find(t, 6), find(t, 8)).val == 6
assert is_balanced(build([1, 2, 3, 4, 5, None, 6]))
assert max_path_sum(build([-3, 9, 20, None, None, 15, -7])) == 41
assert max_path_sum(build([-5])) == -5
assert distribute_coins(build([0, 0, 0, 3, 0, 0, 4])) == 8
assert distribute_coins(build([3, 0, 0])) == 2
assert rob(build([4, 1, 5, 2, None, 1, 3])) == 10
assert height(None) == -1 and is_balanced(None) and diameter(None) == 0 and rob(None) == 0
print("bottom-up checks passed")
import java.util.*;
public class BottomUp {
static final class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
static TreeNode build(Integer[] level) {
if (level.length == 0 || level[0] == null) return null;
TreeNode root = new TreeNode(level[0]);
ArrayDeque<TreeNode> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < level.length) {
TreeNode node = q.poll();
if (i < level.length && level[i] != null) { node.left = new TreeNode(level[i]); q.add(node.left); }
i++;
if (i < level.length && level[i] != null) { node.right = new TreeNode(level[i]); q.add(node.right); }
i++;
}
return root;
}
static TreeNode find(TreeNode n, int val) {
if (n == null || n.val == val) return n;
TreeNode l = find(n.left, val);
return l != null ? l : find(n.right, val);
}
static int height(TreeNode n) { return n == null ? -1 : 1 + Math.max(height(n.left), height(n.right)); }
static int balancedHeight(TreeNode n) { // height, or -2 if unbalanced below
if (n == null) return -1;
int l = balancedHeight(n.left);
if (l == -2) return -2;
int r = balancedHeight(n.right);
if (r == -2 || Math.abs(l - r) > 1) return -2;
return 1 + Math.max(l, r);
}
static boolean isBalanced(TreeNode root) { return balancedHeight(root) != -2; }
record Info(int height, int diameter) {} // tuple return
static Info diam(TreeNode n) {
if (n == null) return new Info(-1, 0);
Info a = diam(n.left), b = diam(n.right);
int through = a.height() + b.height() + 2;
return new Info(1 + Math.max(a.height(), b.height()), Math.max(through, Math.max(a.diameter(), b.diameter())));
}
static int diameter(TreeNode root) { return diam(root).diameter(); }
static int gain(TreeNode n, int[] best) { // side channel: one-element array
if (n == null) return 0;
int l = Math.max(0, gain(n.left, best)), r = Math.max(0, gain(n.right, best));
best[0] = Math.max(best[0], n.val + l + r);
return n.val + Math.max(l, r);
}
static int maxPathSum(TreeNode root) {
int[] best = {Integer.MIN_VALUE};
gain(root, best);
return best[0];
}
static TreeNode lca(TreeNode n, TreeNode p, TreeNode q) {
if (n == null || n == p || n == q) return n;
TreeNode left = lca(n.left, p, q), right = lca(n.right, p, q);
if (left != null && right != null) return n;
return left != null ? left : right;
}
static int excess(TreeNode n, int[] moves) {
if (n == null) return 0;
int l = excess(n.left, moves), r = excess(n.right, moves);
moves[0] += Math.abs(l) + Math.abs(r);
return n.val - 1 + l + r;
}
static int distributeCoins(TreeNode root) {
int[] moves = {0};
excess(root, moves);
return moves[0];
}
record Rob(int take, int skip) {}
static Rob robGo(TreeNode n) {
if (n == null) return new Rob(0, 0);
Rob a = robGo(n.left), b = robGo(n.right);
return new Rob(n.val + a.skip() + b.skip(), Math.max(a.take(), a.skip()) + Math.max(b.take(), b.skip()));
}
static int rob(TreeNode root) { Rob r = robGo(root); return Math.max(r.take(), r.skip()); }
static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }
public static void main(String[] args) {
TreeNode t = build(new Integer[]{1, 2, 3, 4, 5, null, null, 6, null, null, 7, 8, null, null, 9});
check(height(t) == 4 && !isBalanced(t) && diameter(t) == 6, "height/balanced/diameter");
check(lca(t, find(t, 8), find(t, 9)).val == 2, "lca 8 9");
check(lca(t, find(t, 8), find(t, 3)).val == 1, "lca 8 3");
check(lca(t, find(t, 6), find(t, 8)).val == 6, "lca 6 8");
check(isBalanced(build(new Integer[]{1, 2, 3, 4, 5, null, 6})), "balanced");
check(maxPathSum(build(new Integer[]{-3, 9, 20, null, null, 15, -7})) == 41, "max path sum");
check(maxPathSum(build(new Integer[]{-5})) == -5, "negative single");
check(distributeCoins(build(new Integer[]{0, 0, 0, 3, 0, 0, 4})) == 8, "coins");
check(distributeCoins(build(new Integer[]{3, 0, 0})) == 2, "coins small");
check(rob(build(new Integer[]{4, 1, 5, 2, null, 1, 3})) == 10, "rob");
check(height(null) == -1 && isBalanced(null) && diameter(null) == 0 && rob(null) == 0, "empty");
System.out.println("bottom-up checks passed");
}
}
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <optional>
#include <queue>
#include <vector>
struct TreeNode {
int val;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
explicit TreeNode(int v) : val(v) {}
};
std::deque<TreeNode> arena;
TreeNode* make(int v) { arena.emplace_back(v); return &arena.back(); }
TreeNode* build(const std::vector<std::optional<int>>& level) {
if (level.empty() || !level[0]) return nullptr;
TreeNode* root = make(*level[0]);
std::queue<TreeNode*> q;
q.push(root);
size_t i = 1;
while (!q.empty() && i < level.size()) {
TreeNode* node = q.front(); q.pop();
if (i < level.size() && level[i]) { node->left = make(*level[i]); q.push(node->left); }
++i;
if (i < level.size() && level[i]) { node->right = make(*level[i]); q.push(node->right); }
++i;
}
return root;
}
TreeNode* find(TreeNode* n, int val) {
if (!n || n->val == val) return n;
TreeNode* l = find(n->left, val);
return l ? l : find(n->right, val);
}
int height(TreeNode* n) { return n ? 1 + std::max(height(n->left), height(n->right)) : -1; }
int balancedHeight(TreeNode* n) { // height, or -2 if unbalanced below
if (!n) return -1;
int l = balancedHeight(n->left);
if (l == -2) return -2;
int r = balancedHeight(n->right);
if (r == -2 || std::abs(l - r) > 1) return -2;
return 1 + std::max(l, r);
}
bool isBalanced(TreeNode* root) { return balancedHeight(root) != -2; }
struct Info { int height; int diameter; }; // tuple return
Info diam(TreeNode* n) {
if (!n) return {-1, 0};
auto [hl, dl] = diam(n->left); // structured bindings
auto [hr, dr] = diam(n->right);
return {1 + std::max(hl, hr), std::max({dl, dr, hl + hr + 2})};
}
int diameter(TreeNode* root) { return diam(root).diameter; }
int gain(TreeNode* n, int& best) { // side channel: reference parameter
if (!n) return 0;
int l = std::max(0, gain(n->left, best)), r = std::max(0, gain(n->right, best));
best = std::max(best, n->val + l + r);
return n->val + std::max(l, r);
}
int maxPathSum(TreeNode* root) { int best = INT_MIN; gain(root, best); return best; }
TreeNode* lca(TreeNode* n, TreeNode* p, TreeNode* q) {
if (!n || n == p || n == q) return n;
TreeNode* left = lca(n->left, p, q);
TreeNode* right = lca(n->right, p, q);
if (left && right) return n;
return left ? left : right;
}
int excess(TreeNode* n, int& moves) {
if (!n) return 0;
int l = excess(n->left, moves), r = excess(n->right, moves);
moves += std::abs(l) + std::abs(r);
return n->val - 1 + l + r;
}
int distributeCoins(TreeNode* root) { int moves = 0; excess(root, moves); return moves; }
struct Rob { int take; int skip; };
Rob robGo(TreeNode* n) {
if (!n) return {0, 0};
auto [lt, ls] = robGo(n->left);
auto [rt, rs] = robGo(n->right);
return {n->val + ls + rs, std::max(lt, ls) + std::max(rt, rs)};
}
int rob(TreeNode* root) { auto [t, s] = robGo(root); return std::max(t, s); }
int main() {
using std::nullopt;
TreeNode* t = build({1, 2, 3, 4, 5, nullopt, nullopt, 6, nullopt, nullopt, 7, 8, nullopt, nullopt, 9});
assert(height(t) == 4 && !isBalanced(t) && diameter(t) == 6);
assert(lca(t, find(t, 8), find(t, 9))->val == 2);
assert(lca(t, find(t, 8), find(t, 3))->val == 1);
assert(lca(t, find(t, 6), find(t, 8))->val == 6);
assert(isBalanced(build({1, 2, 3, 4, 5, nullopt, 6})));
assert(maxPathSum(build({-3, 9, 20, nullopt, nullopt, 15, -7})) == 41);
assert(maxPathSum(build({-5})) == -5);
assert(distributeCoins(build({0, 0, 0, 3, 0, 0, 4})) == 8);
assert(distributeCoins(build({3, 0, 0})) == 2);
assert(rob(build({4, 1, 5, 2, nullopt, 1, 3})) == 10);
assert(height(nullptr) == -1 && isBalanced(nullptr) && diameter(nullptr) == 0 && rob(nullptr) == 0);
std::cout << "bottom-up checks passed\n";
}
class TreeNode {
val: number;
left: TreeNode | null = null;
right: TreeNode | null = null;
constructor(val: number) {
this.val = val;
}
}
function build(level: (number | null)[]): TreeNode | null {
if (level.length === 0 || level[0] === null) return null;
const root = new TreeNode(level[0]);
const q: TreeNode[] = [root];
let head = 0;
let i = 1;
while (head < q.length && i < level.length) {
const node = q[head++];
const l = level[i++];
if (l !== null && l !== undefined) { node.left = new TreeNode(l); q.push(node.left); }
const r = i < level.length ? level[i] : null;
i++;
if (r !== null && r !== undefined) { node.right = new TreeNode(r); q.push(node.right); }
}
return root;
}
function find(n: TreeNode | null, val: number): TreeNode | null {
if (!n || n.val === val) return n;
return find(n.left, val) ?? find(n.right, val);
}
function height(n: TreeNode | null): number {
return n ? 1 + Math.max(height(n.left), height(n.right)) : -1;
}
function isBalanced(root: TreeNode | null): boolean {
const go = (n: TreeNode | null): number => { // height, or -2 if unbalanced below
if (!n) return -1;
const l = go(n.left);
if (l === -2) return -2;
const r = go(n.right);
if (r === -2 || Math.abs(l - r) > 1) return -2;
return 1 + Math.max(l, r);
};
return go(root) !== -2;
}
function diameter(root: TreeNode | null): number {
const go = (n: TreeNode | null): [number, number] => { // tuple return: [height, diameter]
if (!n) return [-1, 0];
const [hl, dl] = go(n.left);
const [hr, dr] = go(n.right);
return [1 + Math.max(hl, hr), Math.max(dl, dr, hl + hr + 2)];
};
return go(root)[1];
}
function maxPathSum(root: TreeNode | null): number {
let best = -Infinity; // side channel: closure variable
const gain = (n: TreeNode | null): number => {
if (!n) return 0;
const l = Math.max(0, gain(n.left));
const r = Math.max(0, gain(n.right));
best = Math.max(best, n.val + l + r);
return n.val + Math.max(l, r);
};
gain(root);
return best;
}
function lca(n: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
if (!n || n === p || n === q) return n;
const left = lca(n.left, p, q);
const right = lca(n.right, p, q);
if (left && right) return n;
return left ?? right;
}
function distributeCoins(root: TreeNode | null): number {
let moves = 0;
const excess = (n: TreeNode | null): number => {
if (!n) return 0;
const l = excess(n.left);
const r = excess(n.right);
moves += Math.abs(l) + Math.abs(r);
return n.val - 1 + l + r;
};
excess(root);
return moves;
}
function rob(root: TreeNode | null): number {
const go = (n: TreeNode | null): { take: number; skip: number } => {
if (!n) return { take: 0, skip: 0 };
const a = go(n.left);
const b = go(n.right);
return { take: n.val + a.skip + b.skip, skip: Math.max(a.take, a.skip) + Math.max(b.take, b.skip) };
};
const { take, skip } = go(root);
return Math.max(take, skip);
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error(what);
}
const t = build([1, 2, 3, 4, 5, null, null, 6, null, null, 7, 8, null, null, 9]);
check(height(t) === 4 && !isBalanced(t) && diameter(t) === 6, "height/balanced/diameter");
check(lca(t, find(t, 8), find(t, 9))?.val === 2, "lca 8 9");
check(lca(t, find(t, 8), find(t, 3))?.val === 1, "lca 8 3");
check(lca(t, find(t, 6), find(t, 8))?.val === 6, "lca 6 8");
check(isBalanced(build([1, 2, 3, 4, 5, null, 6])), "balanced");
check(maxPathSum(build([-3, 9, 20, null, null, 15, -7])) === 41, "max path sum");
check(maxPathSum(build([-5])) === -5, "negative single");
check(distributeCoins(build([0, 0, 0, 3, 0, 0, 4])) === 8, "coins");
check(distributeCoins(build([3, 0, 0])) === 2, "coins small");
check(rob(build([4, 1, 5, 2, null, 1, 3])) === 10, "rob");
check(height(null) === -1 && isBalanced(null) && diameter(null) === 0 && rob(null) === 0, "empty");
console.log("bottom-up checks passed");
The top-down and structural toolkit:
from collections import Counter, deque
class TreeNode:
def __init__(self, val: int):
self.val = val
self.left: "TreeNode | None" = None
self.right: "TreeNode | None" = None
def build(level):
if not level or level[0] is None:
return None
root = TreeNode(level[0])
q, i = deque([root]), 1
while q and i < len(level):
node = q.popleft()
if i < len(level) and level[i] is not None:
node.left = TreeNode(level[i]); q.append(node.left)
i += 1
if i < len(level) and level[i] is not None:
node.right = TreeNode(level[i]); q.append(node.right)
i += 1
return root
def inorder(n):
return [] if n is None else inorder(n.left) + [n.val] + inorder(n.right)
def good_nodes(root) -> int:
def go(node, best) -> int: # best = max on the path above
if node is None:
return 0
good = 1 if node.val >= best else 0
best = max(best, node.val)
return good + go(node.left, best) + go(node.right, best)
return go(root, float("-inf"))
def has_path_sum(root, target: int) -> bool:
if root is None:
return False
if root.left is None and root.right is None:
return root.val == target
rest = target - root.val
return has_path_sum(root.left, rest) or has_path_sum(root.right, rest)
def path_sum_ii(root, target: int) -> list[list[int]]:
out, path = [], []
def go(node, rest):
if node is None:
return
path.append(node.val)
if node.left is None and node.right is None and node.val == rest:
out.append(path.copy())
go(node.left, rest - node.val)
go(node.right, rest - node.val)
path.pop() # backtrack
go(root, target)
return out
def path_sum_iii(root, target: int) -> int:
freq = Counter({0: 1})
def go(node, s) -> int:
if node is None:
return 0
s += node.val
count = freq[s - target]
freq[s] += 1
count += go(node.left, s) + go(node.right, s)
freq[s] -= 1 # leave the path
return count
return go(root, 0)
def side_views(root) -> tuple[list[int], list[int]]:
left, right, q = [], [], deque([root] if root else [])
while q:
k = len(q)
for i in range(k):
node = q.popleft()
if i == 0: left.append(node.val)
if i == k - 1: right.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return left, right
def invert(node):
if node is not None:
node.left, node.right = invert(node.right), invert(node.left)
return node
def is_symmetric(root) -> bool:
def mirror(a, b) -> bool:
if a is None or b is None:
return a is b
return a.val == b.val and mirror(a.left, b.right) and mirror(a.right, b.left)
return root is None or mirror(root.left, root.right)
def serialize(node) -> str: # separator before every token
return ",#" if node is None else f",{node.val}{serialize(node.left)}{serialize(node.right)}"
def is_subtree(s, t) -> bool:
return serialize(t) in serialize(s)
def flatten(root) -> None: # Morris-style, O(1) extra space
cur = root
while cur:
if cur.left:
tail = cur.left
while tail.right:
tail = tail.right
tail.right = cur.right
cur.right, cur.left = cur.left, None
cur = cur.right
if __name__ == "__main__":
t = build([1, 2, 3, 4, 5, None, None, 6, None, None, 7, 8, None, None, 9])
p = build([1, -2, 3, 4, 1, None, -1, None, None, 2])
assert good_nodes(build([2, 1, 5, 3, None, 2, 6])) == 4
assert has_path_sum(p, 3) and not has_path_sum(p, 5)
assert path_sum_ii(p, 3) == [[1, -2, 4], [1, 3, -1]]
assert path_sum_iii(p, 3) == 4
assert side_views(t) == ([1, 2, 4, 6, 8], [1, 3, 5, 7, 9])
before = inorder(t)
assert inorder(invert(build([1, 2, 3, 4, 5, None, None, 6, None, None, 7, 8, None, None, 9]))) == before[::-1]
assert is_symmetric(build([1, 2, 2, 3, 4, 4, 3]))
assert not is_symmetric(build([1, 2, 2, None, 3, None, 3]))
assert is_subtree(t, build([5, None, 7, None, 9]))
assert not is_subtree(t, build([5, None, 7]))
assert not is_subtree(build([12]), build([2])) # separator prevents a false match
flatten(t)
chain, n = [], t
while n:
assert n.left is None
chain.append(n.val); n = n.right
assert chain == [1, 2, 4, 6, 8, 5, 7, 9, 3]
assert good_nodes(None) == 0 and path_sum_iii(None, 0) == 0 and side_views(None) == ([], [])
print("top-down checks passed")
import java.util.*;
public class TopDown {
static final class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
static TreeNode build(Integer[] level) {
if (level.length == 0 || level[0] == null) return null;
TreeNode root = new TreeNode(level[0]);
ArrayDeque<TreeNode> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < level.length) {
TreeNode node = q.poll();
if (i < level.length && level[i] != null) { node.left = new TreeNode(level[i]); q.add(node.left); }
i++;
if (i < level.length && level[i] != null) { node.right = new TreeNode(level[i]); q.add(node.right); }
i++;
}
return root;
}
static void inorder(TreeNode n, List<Integer> out) {
if (n == null) return;
inorder(n.left, out); out.add(n.val); inorder(n.right, out);
}
static int goodNodes(TreeNode n, int best) {
if (n == null) return 0;
int good = n.val >= best ? 1 : 0;
int nb = Math.max(best, n.val);
return good + goodNodes(n.left, nb) + goodNodes(n.right, nb);
}
static boolean hasPathSum(TreeNode n, int target) {
if (n == null) return false;
if (n.left == null && n.right == null) return n.val == target;
return hasPathSum(n.left, target - n.val) || hasPathSum(n.right, target - n.val);
}
static void pathSum2(TreeNode n, int rest, Deque<Integer> path, List<List<Integer>> out) {
if (n == null) return;
path.addLast(n.val);
if (n.left == null && n.right == null && n.val == rest) out.add(new ArrayList<>(path));
pathSum2(n.left, rest - n.val, path, out);
pathSum2(n.right, rest - n.val, path, out);
path.removeLast(); // backtrack
}
static int pathSum3(TreeNode n, long s, long target, Map<Long, Integer> freq) {
if (n == null) return 0;
s += n.val; // long: sums can exceed int
int count = freq.getOrDefault(s - target, 0);
freq.merge(s, 1, Integer::sum);
count += pathSum3(n.left, s, target, freq) + pathSum3(n.right, s, target, freq);
freq.merge(s, -1, Integer::sum);
return count;
}
static int pathSum3(TreeNode root, int target) {
Map<Long, Integer> freq = new HashMap<>();
freq.put(0L, 1);
return pathSum3(root, 0L, target, freq);
}
record Views(List<Integer> left, List<Integer> right) {}
static Views sideViews(TreeNode root) {
List<Integer> left = new ArrayList<>(), right = new ArrayList<>();
ArrayDeque<TreeNode> q = new ArrayDeque<>();
if (root != null) q.add(root);
while (!q.isEmpty()) {
int k = q.size();
for (int i = 0; i < k; i++) {
TreeNode n = q.poll();
if (i == 0) left.add(n.val);
if (i == k - 1) right.add(n.val);
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
}
return new Views(left, right);
}
static TreeNode invert(TreeNode n) {
if (n == null) return null;
TreeNode l = invert(n.left);
n.left = invert(n.right);
n.right = l;
return n;
}
static boolean mirror(TreeNode a, TreeNode b) {
if (a == null || b == null) return a == b;
return a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
}
static boolean isSymmetric(TreeNode root) { return root == null || mirror(root.left, root.right); }
static void serialize(TreeNode n, StringBuilder sb) { // separator before every token
if (n == null) { sb.append(",#"); return; }
sb.append(',').append(n.val);
serialize(n.left, sb);
serialize(n.right, sb);
}
static boolean isSubtree(TreeNode s, TreeNode t) {
StringBuilder a = new StringBuilder(), b = new StringBuilder();
serialize(s, a);
serialize(t, b);
return a.indexOf(b.toString()) >= 0; // naive matcher: use KMP for a guarantee
}
static void flatten(TreeNode root) {
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
TreeNode tail = cur.left;
while (tail.right != null) tail = tail.right;
tail.right = cur.right;
cur.right = cur.left;
cur.left = null;
}
cur = cur.right;
}
}
static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }
public static void main(String[] args) {
Integer[] tl = {1, 2, 3, 4, 5, null, null, 6, null, null, 7, 8, null, null, 9};
TreeNode t = build(tl);
TreeNode p = build(new Integer[]{1, -2, 3, 4, 1, null, -1, null, null, 2});
check(goodNodes(build(new Integer[]{2, 1, 5, 3, null, 2, 6}), Integer.MIN_VALUE) == 4, "good nodes");
check(hasPathSum(p, 3) && !hasPathSum(p, 5), "path sum I");
List<List<Integer>> ps2 = new ArrayList<>();
pathSum2(p, 3, new ArrayDeque<>(), ps2);
check(ps2.equals(List.of(List.of(1, -2, 4), List.of(1, 3, -1))), "path sum II");
check(pathSum3(p, 3) == 4, "path sum III");
Views v = sideViews(t);
check(v.left().equals(List.of(1, 2, 4, 6, 8)) && v.right().equals(List.of(1, 3, 5, 7, 9)), "views");
List<Integer> before = new ArrayList<>(), after = new ArrayList<>();
inorder(t, before);
inorder(invert(build(tl)), after);
Collections.reverse(before);
check(before.equals(after), "invert");
check(isSymmetric(build(new Integer[]{1, 2, 2, 3, 4, 4, 3})), "symmetric");
check(!isSymmetric(build(new Integer[]{1, 2, 2, null, 3, null, 3})), "not symmetric");
check(isSubtree(t, build(new Integer[]{5, null, 7, null, 9})), "subtree");
check(!isSubtree(t, build(new Integer[]{5, null, 7})), "not subtree");
check(!isSubtree(build(new Integer[]{12}), build(new Integer[]{2})), "separator");
flatten(t);
List<Integer> chain = new ArrayList<>();
for (TreeNode n = t; n != null; n = n.right) { check(n.left == null, "left null"); chain.add(n.val); }
check(chain.equals(List.of(1, 2, 4, 6, 8, 5, 7, 9, 3)), "flatten");
check(goodNodes(null, 0) == 0 && pathSum3(null, 0) == 0 && sideViews(null).left().isEmpty(), "empty");
System.out.println("top-down checks passed");
}
}
#include <algorithm>
#include <cassert>
#include <climits>
#include <deque>
#include <iostream>
#include <optional>
#include <queue>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
struct TreeNode {
int val;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
explicit TreeNode(int v) : val(v) {}
};
std::deque<TreeNode> arena;
TreeNode* make(int v) { arena.emplace_back(v); return &arena.back(); }
TreeNode* build(const std::vector<std::optional<int>>& level) {
if (level.empty() || !level[0]) return nullptr;
TreeNode* root = make(*level[0]);
std::queue<TreeNode*> q;
q.push(root);
size_t i = 1;
while (!q.empty() && i < level.size()) {
TreeNode* node = q.front(); q.pop();
if (i < level.size() && level[i]) { node->left = make(*level[i]); q.push(node->left); }
++i;
if (i < level.size() && level[i]) { node->right = make(*level[i]); q.push(node->right); }
++i;
}
return root;
}
void inorder(TreeNode* n, std::vector<int>& out) {
if (!n) return;
inorder(n->left, out); out.push_back(n->val); inorder(n->right, out);
}
int goodNodes(TreeNode* n, int best) {
if (!n) return 0;
int good = n->val >= best ? 1 : 0;
int nb = std::max(best, n->val);
return good + goodNodes(n->left, nb) + goodNodes(n->right, nb);
}
bool hasPathSum(TreeNode* n, int target) {
if (!n) return false;
if (!n->left && !n->right) return n->val == target;
return hasPathSum(n->left, target - n->val) || hasPathSum(n->right, target - n->val);
}
void pathSum2(TreeNode* n, int rest, std::vector<int>& path, std::vector<std::vector<int>>& out) {
if (!n) return;
path.push_back(n->val);
if (!n->left && !n->right && n->val == rest) out.push_back(path);
pathSum2(n->left, rest - n->val, path, out);
pathSum2(n->right, rest - n->val, path, out);
path.pop_back(); // backtrack
}
int pathSum3(TreeNode* n, long long s, long long target, std::unordered_map<long long, int>& freq) {
if (!n) return 0;
s += n->val; // 64-bit: sums can exceed int
auto it = freq.find(s - target);
int count = it == freq.end() ? 0 : it->second;
++freq[s];
count += pathSum3(n->left, s, target, freq) + pathSum3(n->right, s, target, freq);
--freq[s];
return count;
}
int pathSum3(TreeNode* root, int target) {
std::unordered_map<long long, int> freq{{0, 1}};
return pathSum3(root, 0, target, freq);
}
std::pair<std::vector<int>, std::vector<int>> sideViews(TreeNode* root) {
std::vector<int> left, right;
std::queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
size_t k = q.size();
for (size_t i = 0; i < k; ++i) {
TreeNode* n = q.front(); q.pop();
if (i == 0) left.push_back(n->val);
if (i == k - 1) right.push_back(n->val);
if (n->left) q.push(n->left);
if (n->right) q.push(n->right);
}
}
return {left, right};
}
TreeNode* invert(TreeNode* n) {
if (!n) return nullptr;
TreeNode* l = invert(n->left);
n->left = invert(n->right);
n->right = l;
return n;
}
bool mirror(TreeNode* a, TreeNode* b) {
if (!a || !b) return a == b;
return a->val == b->val && mirror(a->left, b->right) && mirror(a->right, b->left);
}
bool isSymmetric(TreeNode* root) { return !root || mirror(root->left, root->right); }
void serialize(TreeNode* n, std::string& out) { // separator before every token
if (!n) { out += ",#"; return; }
out += ',';
out += std::to_string(n->val);
serialize(n->left, out);
serialize(n->right, out);
}
bool isSubtree(TreeNode* s, TreeNode* t) {
std::string a, b;
serialize(s, a);
serialize(t, b);
return a.find(b) != std::string::npos; // use KMP for a worst-case guarantee
}
void flatten(TreeNode* root) {
for (TreeNode* cur = root; cur; cur = cur->right) {
if (cur->left) {
TreeNode* tail = cur->left;
while (tail->right) tail = tail->right;
tail->right = cur->right;
cur->right = cur->left;
cur->left = nullptr;
}
}
}
int main() {
using std::nullopt;
const std::vector<std::optional<int>> tl{1, 2, 3, 4, 5, nullopt, nullopt, 6, nullopt, nullopt, 7, 8, nullopt, nullopt, 9};
TreeNode* t = build(tl);
TreeNode* p = build({1, -2, 3, 4, 1, nullopt, -1, nullopt, nullopt, 2});
assert(goodNodes(build({2, 1, 5, 3, nullopt, 2, 6}), INT_MIN) == 4);
assert(hasPathSum(p, 3) && !hasPathSum(p, 5));
std::vector<int> path;
std::vector<std::vector<int>> ps2;
pathSum2(p, 3, path, ps2);
assert((ps2 == std::vector<std::vector<int>>{{1, -2, 4}, {1, 3, -1}}));
assert(pathSum3(p, 3) == 4);
auto [lv, rv] = sideViews(t);
assert((lv == std::vector<int>{1, 2, 4, 6, 8} && rv == std::vector<int>{1, 3, 5, 7, 9}));
std::vector<int> before, after;
inorder(t, before);
inorder(invert(build(tl)), after);
std::reverse(before.begin(), before.end());
assert(before == after);
assert(isSymmetric(build({1, 2, 2, 3, 4, 4, 3})));
assert(!isSymmetric(build({1, 2, 2, nullopt, 3, nullopt, 3})));
assert(isSubtree(t, build({5, nullopt, 7, nullopt, 9})));
assert(!isSubtree(t, build({5, nullopt, 7})));
assert(!isSubtree(build({12}), build({2})));
flatten(t);
std::vector<int> chain;
for (TreeNode* n = t; n; n = n->right) { assert(!n->left); chain.push_back(n->val); }
assert((chain == std::vector<int>{1, 2, 4, 6, 8, 5, 7, 9, 3}));
assert(goodNodes(nullptr, 0) == 0 && pathSum3(nullptr, 0) == 0 && sideViews(nullptr).first.empty());
std::cout << "top-down checks passed\n";
}
class TreeNode {
val: number;
left: TreeNode | null = null;
right: TreeNode | null = null;
constructor(val: number) {
this.val = val;
}
}
function build(level: (number | null)[]): TreeNode | null {
if (level.length === 0 || level[0] === null) return null;
const root = new TreeNode(level[0]);
const q: TreeNode[] = [root];
let head = 0;
let i = 1;
while (head < q.length && i < level.length) {
const node = q[head++];
const l = level[i++];
if (l !== null && l !== undefined) { node.left = new TreeNode(l); q.push(node.left); }
const r = i < level.length ? level[i] : null;
i++;
if (r !== null && r !== undefined) { node.right = new TreeNode(r); q.push(node.right); }
}
return root;
}
function inorder(n: TreeNode | null, out: number[] = []): number[] {
if (n) { inorder(n.left, out); out.push(n.val); inorder(n.right, out); }
return out;
}
function goodNodes(root: TreeNode | null): number {
const go = (n: TreeNode | null, best: number): number => {
if (!n) return 0;
const good = n.val >= best ? 1 : 0;
const nb = Math.max(best, n.val);
return good + go(n.left, nb) + go(n.right, nb);
};
return go(root, -Infinity);
}
function hasPathSum(n: TreeNode | null, target: number): boolean {
if (!n) return false;
if (!n.left && !n.right) return n.val === target;
return hasPathSum(n.left, target - n.val) || hasPathSum(n.right, target - n.val);
}
function pathSumII(root: TreeNode | null, target: number): number[][] {
const out: number[][] = [];
const path: number[] = [];
const go = (n: TreeNode | null, rest: number): void => {
if (!n) return;
path.push(n.val);
if (!n.left && !n.right && n.val === rest) out.push([...path]);
go(n.left, rest - n.val);
go(n.right, rest - n.val);
path.pop(); // backtrack
};
go(root, target);
return out;
}
function pathSumIII(root: TreeNode | null, target: number): number {
const freq = new Map<number, number>([[0, 1]]);
const go = (n: TreeNode | null, s: number): number => {
if (!n) return 0;
s += n.val;
let count = freq.get(s - target) ?? 0;
freq.set(s, (freq.get(s) ?? 0) + 1);
count += go(n.left, s) + go(n.right, s);
freq.set(s, freq.get(s)! - 1);
return count;
};
return go(root, 0);
}
function sideViews(root: TreeNode | null): [number[], number[]] {
const left: number[] = [];
const right: number[] = [];
let level: TreeNode[] = root ? [root] : [];
while (level.length) {
left.push(level[0].val);
right.push(level[level.length - 1].val);
const next: TreeNode[] = [];
for (const n of level) {
if (n.left) next.push(n.left);
if (n.right) next.push(n.right);
}
level = next;
}
return [left, right];
}
function invert(n: TreeNode | null): TreeNode | null {
if (n) {
const l = invert(n.left);
n.left = invert(n.right);
n.right = l;
}
return n;
}
function isSymmetric(root: TreeNode | null): boolean {
const mirror = (a: TreeNode | null, b: TreeNode | null): boolean => {
if (!a || !b) return a === b;
return a.val === b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
};
return !root || mirror(root.left, root.right);
}
function serialize(n: TreeNode | null): string {
return n ? `,${n.val}${serialize(n.left)}${serialize(n.right)}` : ",#"; // separator before every token
}
function isSubtree(s: TreeNode | null, t: TreeNode | null): boolean {
return serialize(s).includes(serialize(t));
}
function flatten(root: TreeNode | null): void {
for (let cur = root; cur; cur = cur.right) {
if (cur.left) {
let tail = cur.left;
while (tail.right) tail = tail.right;
tail.right = cur.right;
cur.right = cur.left;
cur.left = null;
}
}
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error(what);
}
const same = (a: unknown, b: unknown): boolean => JSON.stringify(a) === JSON.stringify(b);
const tl = [1, 2, 3, 4, 5, null, null, 6, null, null, 7, 8, null, null, 9];
const t = build(tl);
const p = build([1, -2, 3, 4, 1, null, -1, null, null, 2]);
check(goodNodes(build([2, 1, 5, 3, null, 2, 6])) === 4, "good nodes");
check(hasPathSum(p, 3) && !hasPathSum(p, 5), "path sum I");
check(same(pathSumII(p, 3), [[1, -2, 4], [1, 3, -1]]), "path sum II");
check(pathSumIII(p, 3) === 4, "path sum III");
check(same(sideViews(t), [[1, 2, 4, 6, 8], [1, 3, 5, 7, 9]]), "views");
check(same(inorder(invert(build(tl))), inorder(t).reverse()), "invert");
check(isSymmetric(build([1, 2, 2, 3, 4, 4, 3])), "symmetric");
check(!isSymmetric(build([1, 2, 2, null, 3, null, 3])), "not symmetric");
check(isSubtree(t, build([5, null, 7, null, 9])), "subtree");
check(!isSubtree(t, build([5, null, 7])), "not subtree");
check(!isSubtree(build([12]), build([2])), "separator");
flatten(t);
const chain: number[] = [];
for (let n = t; n; n = n.right) { check(n.left === null, "left null"); chain.push(n.val); }
check(same(chain, [1, 2, 4, 6, 8, 5, 7, 9, 3]), "flatten");
check(goodNodes(null) === 0 && pathSumIII(null, 0) === 0 && sideViews(null)[0].length === 0, "empty");
console.log("top-down checks passed");
Variant: right side view by DFS
The DFS form of the right view records the first node seen at each depth while visiting right children first. It uses space instead of BFS's and is the same top-down template with depth as the state:
class T:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def right_view_dfs(root) -> list[int]:
out: list[int] = []
def go(node, depth):
if node is None:
return
if depth == len(out): # first node reached at this depth
out.append(node.val)
go(node.right, depth + 1) # right first
go(node.left, depth + 1)
go(root, 0)
return out
ex = T(1, T(2, T(4, T(6, T(8))), T(5, None, T(7, None, T(9)))), T(3))
assert right_view_dfs(ex) == [1, 3, 5, 7, 9]
assert right_view_dfs(T(1, T(2, T(4)))) == [1, 2, 4] # left nodes visible when the right is empty
Real-world uses
Compilers: inherited and synthesized attributes. Type checking computes each expression's type from its children's (bottom-up); scope resolution passes the environment of visible names down into nested blocks (top-down). Constant folding is bottom-up; tracking whether code is inside a loop (to validate break) is top-down. Knuth's attribute grammars are exactly this page's two templates, and hash-consing — interning structurally equal subtrees so they share one node — is how compilers and symbolic-algebra systems detect common subexpressions, the same technique as the interned subtree check above.
UI layout. Flutter's layout protocol is literally "constraints go down, sizes go up, parent sets position": a top-down pass of constraints, a bottom-up return of sizes, then the parent places children. Browser layout is similar in spirit — available width flows down the box tree and content heights flow up — and CSS property inheritance (color, font-family) is a top-down pass over the DOM.
File systems and storage. du aggregates sizes bottom-up; permission inheritance (NTFS inheritable ACEs, default ACLs on POSIX directories) flows top-down. Version control relies on subtree hashing: a Git tree object's id is the hash of its entries, including the ids of its subtrees, so two identical directories anywhere in history share an id and git diff can skip identical subtrees without descending — a Merkle tree (Hashing Algorithms). Amazon's Dynamo paper and Cassandra's anti-entropy repair compare Merkle trees between replicas to find differing key ranges by descending only into subtrees whose hashes differ (Gossip Protocols).
Lowest common ancestors. The DOM Range API exposes commonAncestorContainer, the LCA of a selection's endpoints. git merge-base finds a best common ancestor of two commits — the same idea generalised to a DAG. In bioinformatics the most recent common ancestor in a phylogenetic tree is an LCA query, and in networking, the LCA in a hierarchical topology (racks under switches under spines) bounds the path between two hosts.
Databases and query plans. A query plan is a tree; cost estimation is bottom-up (a join's cost depends on its inputs' estimated cardinalities), and pushing a predicate down toward the scans is a top-down rewrite (Query Planning & Optimization).
Pitfalls & edge cases
- Wrong null base case. Height of null is (edges) or 0 (nodes) — mixing them makes the diameter off by two. Max-path gain of null is 0, but the global best starts at .
- Answer only at the root. Diameter and max path sum can bend at any node; computing only at the root fails on the example (5 instead of 6).
- Min depth with one child. treats a missing child as a leaf at depth 0. Only real leaves end a path.
- Path Sum I with an empty tree and target 0. An empty tree has no root-to-leaf paths, so the answer is false, not true.
- Pruning with negative numbers. "Stop when the running sum exceeds the target" is wrong when values can be negative.
- Forgetting to undo state. In Path Sum II, pop the path on exit; in Path Sum III, decrement the frequency on exit. Missing either counts paths that jump between branches.
- Integer overflow in path sums. LeetCode 437 has node values up to in magnitude, so a path of a few nodes overflows 32-bit
int. Uselong/long long; JavaScript numbers are exact up to . - Comparing values instead of nodes. LCA must compare node identity (
node is p) when values repeat. - LCA when a target is missing. The basic recursion returns the present node as if it were the answer.
- Subtree serialization without separators or null markers. Without a leading separator,
2matches inside12; without null markers, a tree matches a prefix of a larger one (5 → 7"matches"5 → 7 → 9). - Invert with inorder. Swapping during inorder processes one subtree twice and the other never.
- Flatten order. Attaching the right subtree to the tail of the left subtree (its rightmost node) preserves preorder; attaching it to
cur.leftdirectly does not. - Recursion depth. Every recursive solution here is deep; skewed inputs of nodes need the iterative forms.
Variations
- -ary trees. Both templates generalise: loop over children instead of left/right. Diameter becomes "the two largest child heights plus 2"; LCA counts how many children returned non-null.
- Unrooted trees (graphs). For diameter, double BFS (farthest from any node, then farthest from that) works on any tree; the bottom-up version works after choosing an arbitrary root. See Graphs.
- Many LCA queries. Binary lifting ( per query after preprocessing) or Euler tour + sparse table ( per query): LCA, Binary Lifting & Euler Tour.
- Path queries with updates. Sums or maxima on arbitrary paths with updates need heavy-light decomposition over a segment tree: Heavy-Light & Centroid Decomposition.
- Answers for every root. "Sum of distances from every node" or "height of the tree rooted at each node" need rerooting: two passes, one bottom-up and one top-down that pushes the parent's contribution into each child. That is Module 6's Tree DP & Rerooting.
- Duplicate subtrees. Interning (or serialization into a hash map) finds every subtree shape that occurs more than once in expected (LeetCode 652).
- Path sum variants. Count paths with sum in a range (prefix sums plus an ordered structure), longest path with equal values (bottom-up, like diameter), paths with an XOR target (prefix XOR instead of prefix sum).
Practice ladder
Each problem is described in my own words. Solutions are Python and run as part of this page's checks.
- Maximum Depth of Binary Tree (LeetCode 104) — Easy. Count nodes on the longest root-to-leaf path. Teaches the bottom-up base case.
Hint
Null has depth 0; a node has depth one more than its deeper child.
- Invert Binary Tree (LeetCode 226) — Easy. Mirror the tree. Teaches that any non-inorder traversal works for local rewrites.
Hint
Swap the children of every node, recursing after (or before) the swap.
- Symmetric Tree (LeetCode 101) — Easy. Is the tree its own mirror? Teaches recursion on pairs.
Hint
mirror(a, b): both null, or equal values and mirror(a.left, b.right) and mirror(a.right, b.left).
- Path Sum (LeetCode 112) — Easy. Is there a root-to-leaf path with the given sum? Teaches top-down remaining sum and the leaf test.
Hint
Subtract as you go down; check equality only at a leaf. The empty tree returns false.
- Balanced Binary Tree (LeetCode 110) — Easy. Decide height balance in . Teaches the sentinel return.
Hint
Return the height, or a sentinel such as the moment any subtree is unbalanced, and propagate it.
- Diameter of Binary Tree (LeetCode 543) — Easy. Longest path in edges. Teaches return-one, record-another.
Hint
Return height; at each node record left_height + right_height + 2 (with null height ) in a global.
- Subtree of Another Tree (LeetCode 572) — Easy. Is one tree a subtree of the other? Teaches naive matching versus serialization versus interning.
Hint
Serialize both in preorder with null markers and a separator before every token, then test substring containment.
Solution
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def is_subtree(root, sub) -> bool:
def ser(n, out):
if n is None:
out.append(",#")
else:
out.append("," + str(n.val)); ser(n.left, out); ser(n.right, out)
return out
return "".join(ser(sub, [])) in "".join(ser(root, []))
s = Node(3, Node(4, Node(1), Node(2)), Node(5))
assert is_subtree(s, Node(4, Node(1), Node(2)))
assert not is_subtree(Node(3, Node(4, Node(1), Node(2, Node(0))), Node(5)), Node(4, Node(1), Node(2)))
assert not is_subtree(Node(12), Node(2))
to serialize; the containment test is linear in CPython for long needles. In Java or C++ replace contains/find with KMP for a worst-case guarantee.
- Binary Tree Right Side View (LeetCode 199) — Medium. The last node of each level. Teaches BFS with the snapshot, or right-first DFS by depth.
Hint
BFS: append the last node of each level. DFS: visit right before left and append a node when its depth equals the answer's length.
- Count Good Nodes in Binary Tree (LeetCode 1448) — Medium. Count nodes not smaller than any ancestor. Teaches top-down with a path statistic.
Hint
Pass the maximum value seen on the path so far.
- Path Sum II (LeetCode 113) — Medium. List all root-to-leaf paths with the sum. Teaches backtracking with one shared list.
Hint
Append on entry, pop on exit, copy at a matching leaf.
- Path Sum III (LeetCode 437) — Medium. Count downward paths with the sum, starting anywhere. Teaches prefix sums on a path with a backtracked hash map.
Hint
Seed `freq = {0: 1}`. At each node add `freq[prefix - target]`, increment `freq[prefix]`, recurse, decrement. Use 64-bit sums.
- Lowest Common Ancestor of a Binary Tree (LeetCode 236) — Medium. Deepest node with both targets below it. Teaches the "return what you found" contract.
Hint
Return the node if it is null, <span class="math" data-tex="p"></span> or <span class="math" data-tex="q"></span>. Otherwise, if both recursive calls return non-null, this node is the answer; else pass up the non-null one.
Solution
```python
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def lowest_common_ancestor(root, p, q):
if root is None or root is p or root is q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
return root if left and right else (left or right)
n8, n9, n3 = Node(8), Node(9), Node(3)
n6 = Node(6, n8)
root = Node(1, Node(2, Node(4, n6), Node(5, None, Node(7, None, n9))), n3)
assert lowest_common_ancestor(root, n8, n9).val == 2
assert lowest_common_ancestor(root, n8, n3) is root
assert lowest_common_ancestor(root, n6, n8) is n6
```
<span class="math" data-tex="O(n)"></span> time, <span class="math" data-tex="O(h)"></span> space. The proof in the Correctness section requires both targets to be present, which this problem guarantees.
- Flatten Binary Tree to Linked List (LeetCode 114) — Medium. Rewire in place into preorder via
rightpointers. Teaches reverse postorder or Morris-style rewiring.
Hint
For <span class="math" data-tex="O(1)"></span> space: at each node with a left child, hang the right subtree off the rightmost node of the left subtree, move left to right, continue right.
- Distribute Coins in Binary Tree (LeetCode 979) — Medium. Minimum moves so every node has one coin. Teaches bottom-up excess and the cut argument.
Hint
A subtree with <span class="math" data-tex="c"></span> coins and <span class="math" data-tex="k"></span> nodes must send <span class="math" data-tex="c - k"></span> coins across the edge above it (or receive <span class="math" data-tex="k - c"></span>). Sum the absolute values.
Solution
```python
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def distribute_coins(root) -> int:
moves = 0
def excess(node) -> int:
nonlocal moves
if node is None:
return 0
l, r = excess(node.left), excess(node.right)
moves += abs(l) + abs(r) # coins crossing the two child edges
return node.val + l + r - 1
excess(root)
return moves
assert distribute_coins(Node(3, Node(0), Node(0))) == 2
assert distribute_coins(Node(0, Node(3), Node(0))) == 3
assert distribute_coins(Node(0, Node(0, Node(3), Node(0)), Node(0, Node(0), Node(4)))) == 8
```
<span class="math" data-tex="O(n)"></span> time, <span class="math" data-tex="O(h)"></span> space. Each edge's count is a lower bound by the cut argument and all are achieved simultaneously.
- Binary Tree Maximum Path Sum (LeetCode 124) — Hard. Best path sum anywhere, negatives allowed. Teaches gain versus bend, and initialisation. Follow it with House Robber III (LeetCode 337) for the tuple-return tree DP preview.
Hint
`gain(v) = v.val + max(0, gain(L), gain(R))`; record `v.val + max(0, gain(L)) + max(0, gain(R))`.
Solution
```python
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def max_path_sum(root) -> int:
best = float("-inf")
def gain(node) -> int:
nonlocal best
if node is None:
return 0
l = max(0, gain(node.left))
r = max(0, gain(node.right))
best = max(best, node.val + l + r) # path bending at node
return node.val + max(l, r) # path continuing to the parent
gain(root)
return best
assert max_path_sum(Node(-3, Node(9), Node(20, Node(15), Node(-7)))) == 41
assert max_path_sum(Node(-5)) == -5
assert max_path_sum(Node(2, Node(-1), Node(-2))) == 2
```
<span class="math" data-tex="O(n)"></span> time, <span class="math" data-tex="O(h)"></span> space.
Common mistakes & interview follow-ups
"Your diameter is wrong on this tree." The usual cause is computing only at the root, or mixing edge and node counts. Say the definition (edges) and the null height out loud.
"Can you do it without a global variable?" Return a tuple: (height, best_inside) for diameter, (gain, best_inside) for max path sum. Show the language idiom (record, struct with structured bindings, tuple destructuring).
"What if or might not be in the tree?" Return a (node, count) pair, or run a presence check first; only report the LCA if both were found.
"What if the tree has parent pointers?" LCA becomes the intersection of two linked lists: walk both upward, switching to the other start when one reaches the root — the two-pointer trick from Linked Lists — in time and space.
"What if there are a million LCA queries?" Preprocess with binary lifting or an Euler tour; see LCA, Binary Lifting & Euler Tour.
"Path Sum III, but paths can go up and down (any path)?" That is a much harder problem; the standard approach is centroid decomposition, or (Heavy-Light & Centroid Decomposition).
"Make it iterative." Postorder with the visited-flag template, storing each node's returned summary in a map (or on the stack beside the node).
Common mistakes seen in interviews: using 1 + min for minimum depth; initialising the max-path-sum best to 0; forgetting freq[s] -= 1; comparing node values instead of identity in LCA; serializing without null markers in the subtree check; declaring an solution because "each call is " while calling height inside the recursion.
Quick quiz
- A node has left height 3 and right height (no right child). What is the longest path whose highest node is this one, in edges?
Answer
: the edge down to the left child plus the left subtree's height of 3.
- Why must
bestin maximum path sum start at butgain(null)be 0?
Answer
gain(null) = 0 encodes "a path may stop here and contribute nothing", which is always allowed. best must start below every possible answer because every path contains at least one node and all values may be negative; starting at 0 would report 0 for a tree of negatives.
- In Path Sum III, what goes wrong if you forget to decrement
freq[s]after recursing?
Answer
Prefix sums from a finished branch remain in the map, so a node in a sibling branch can match a "prefix" that is not its ancestor, counting paths that are not downward paths.
- The LCA recursion returns node for the whole tree. What are the two possible meanings, and how do you tell them apart?
Answer
Either is a descendant of (so is the true LCA), or is not in the tree. The recursion cannot distinguish them; return a found-count alongside the node, or check 's presence separately.
- Which of these must be top-down: (a) height, (b) count of good nodes, (c) diameter, (d) right side view by DFS?
Answer
(b) and (d). Good nodes depend on the path's maximum above each node; the DFS right view needs the current depth passed down. Height and diameter depend only on subtrees.
Further reading / sources
- Knuth, "Semantics of context-free languages", Mathematical Systems Theory 2(2), 1968 — inherited and synthesized attributes.
- Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Chapter 12 (binary search trees) and the disjoint-sets chapter's problem on Tarjan's off-line LCA algorithm (Problem 21-3 in the 3rd edition).
- Sedgewick & Wayne, Algorithms, 4th ed., §3.2 (recursive BST methods returning values up the tree).
- Aho, Lam, Sethi & Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., Chapter 5 "Syntax-Directed Translation" (synthesized and inherited attributes) and §6.1.2 (value numbering / DAGs for expressions).
- DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store", SOSP 2007 — Merkle trees for anti-entropy.
- Flutter documentation: Understanding constraints — "constraints go down, sizes go up, parent sets position".
- cp-algorithms: Lowest Common Ancestor and Wikipedia: Lowest common ancestor.
Prev: Binary Trees & Traversals · Next: Binary Search Trees
Related: Module 3 · Trees · Trees (Overview) · Prefix Sums & Difference Arrays · Recursion & Mathematical Induction · LCA, Binary Lifting & Euler Tour · Graphs · Dynamic Programming · Linked Lists · DSA: Zero to Mastery