4.14.0 — Trees: The Pattern

Recognition cue. The input is a tree. The real question is always the same one:

What does this node do, and what does it need from its children?

Answer that and the code writes itself. Almost every problem here is a traversal with different work done at the node.

The two directions

This is the frame that makes the whole chapter easy, and it is worth deciding before writing a line.

Information flowing UP — return it. Depths, sums, counts, validity. The node cannot answer until its children have. This is post-order.

Information flowing DOWN — pass it as a parameter. The maximum seen on the path, an allowed range, the depth so far. Each branch gets its own copy, so no undo is needed.

Several problems do both: a range goes down, a count comes up.

The one structure that catches people

For the harder problems, what the function returns is not what the problem asks for.

• Diameter returns the depth, records the best turning point.
• Maximum Path Sum returns the best one-sided sum, records the best two-sided sum.

The reason is always the same: a parent can only extend a path through one child, but the answer is allowed to turn around and use both. Two different numbers, so one is returned and the other kept on the side.

Return what the parent needs; record what the question wants.

The three templates

# 1. DFS, information up (post-order)
def solve(node):
    if not node: return base_value
    left = solve(node.left)
    right = solve(node.right)
    return combine(node.val, left, right)

# 2. DFS, information down
def solve(node, state):
    if not node: return
    new_state = update(state, node)
    solve(node.left, new_state)
    solve(node.right, new_state)

# 3. BFS, level by level
queue = deque([root])
while queue:
    for _ in range(len(queue)):        # ← freeze the level size FIRST
        node = queue.popleft()
        ...
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)

DFS or BFS?

use	when	space
DFS	the answer depends on subtrees — depth, sums, paths, validation	O(h)
BFS	the answer depends on levels, or you want the shallowest and can stop early	O(w)

On a balanced tree the last level holds about half the nodes, so BFS is O(n) and DFS is O(\log n). On a degenerate tree it reverses. Say "height", not "log n", unless balance is promised.

The fifteen problems

#	Problem	The one insight
4.14.1	Invert Binary Tree ★	Swap here, trust the recursion below
4.14.2	Maximum Depth ★	1 + max(left, right)
4.14.3	Diameter	Return depth, record the turning point
4.14.4	Balanced Binary Tree	One pass, -1 as the failure sentinel
4.14.5	Same Tree ★	Recurse on both trees at once
4.14.6	Subtree of Another Tree ★	Same Tree tried at every node
4.14.7	LCA of a BST ★	Walk to the split point; ordering replaces searching
4.14.8	Level Order Traversal ★	Freeze len(queue) to bound the level
4.14.9	Right Side View ★	The last node of each level
4.14.10	Count Good Nodes	Carry the path maximum down
4.14.11	Validate BST ★	Carry a (low, high) range down — subtrees, not children
4.14.12	Kth Smallest in a BST ★	In-order gives sorted output; stop at k
4.14.13	Construct from Preorder + Inorder ★	Pre-order gives the root, in-order gives the split
4.14.14	Maximum Path Sum ★	Clamp negative branches to zero
4.14.15	Serialize and Deserialize ★	Null markers make one traversal enough

★ marks the Blind 75 subset.

The traps on this pattern

Validating a BST by comparing parent and child. The property is about entire subtrees. See the counterexample on 4.14.11.

Forgetting to freeze the level size in BFS. Children added mid-loop change len(queue) and the level boundary is lost.

Edges versus nodes. Diameter counts edges; depth counts nodes. They differ by one and the problem statement decides which.

Recomputing depth at every node. That is the O(n^2) trap in Balanced Binary Tree; compute each depth once on the way up.

Assuming O(\log n) space. It is O(h), and h is n on a degenerate tree.

Using pop(0) as a queue. O(n) in Python. Use collections.deque.

What the interviewer will push on

"Does information flow up or down here?" Say it before coding. It picks the template.

"Why does your function return something different from the answer?" The parent can only extend one side.

"Why is checking parent against child not enough for a BST?" The counterexample.

"How do you know where a BFS level ends?" The frozen length.

"Which uses more memory, DFS or BFS?" O(h) against O(w), and which is worse depends on the tree's shape.

One thing to volunteer: state the recursion in one English sentence before writing it. "The depth of a tree is one more than the depth of its deeper subtree." If you cannot produce that sentence, the code will not be right either.

Recall

• The question is always what does this node do, and what does it need from its children.
• Up = return value (post-order). Down = parameter. Many problems use both.
• Hard problems return one thing and record another, because a parent can extend only one side while the answer may turn around and use both.
• BFS levels need the queue length frozen before the inner loop.
• In-order on a BST gives sorted output — that fact solves validation, k-th smallest, and range queries.
• Validate a BST with a (low, high) range carried down. Comparing parent to child is the classic wrong answer.
• Space is O(h) for DFS and O(w) for BFS; on a balanced tree that is O(\log n) against O(n).
• One traversal plus null markers determines a tree; without markers you need two traversals.

Next: 4.14.1 Invert Binary Tree — the simplest possible version of "do something here, then recurse".