Structure and paths
Write height, diameter and maximum path sum as one postorder shape by separating what a call returns from what it records, then rebuild a tree from traversals.
Most tree problems that sound different are one function with a different middle line. A postorder call returns the single fact its parent needs; on the way past, it updates an answer the parent never sees. Once you can name those two things separately, height, diameter and maximum path sum stop being three problems.
The failure mode is running them together — returning the thing you wanted to record. That produces code that looks right, passes a symmetric example, and is wrong on the first tree that bends.
The shape
def solve(root):
best = <identity>
def go(node): # returns: what the PARENT can use
nonlocal best
if node is None:
return <base>
l = go(node.left)
r = go(node.right)
best = combine(best, l, r, node) # what the ANSWER needs
return extend(l, r, node) # what the parent needs
go(root)
return best
Two lines carry all the variation. combine may use both children, because this
node is where the two sides meet. extend may use only one, because a parent
that hangs a path off this node can go down one branch, not both. Everything else
is the postorder walk unchanged.
Three problems, one shape
Height needs nothing recorded — the return is already the answer:
def height(root):
def go(node):
if node is None:
return 0
return 1 + max(go(node.left), go(node.right))
return go(root)
Diameter is the longest path in edges between any two nodes. It is the same walk
with the best line added:
def diameter(root):
best = 0
def go(node): # returns: height of this subtree
nonlocal best
if node is None:
return 0
l, r = go(node.left), go(node.right)
best = max(best, l + r) # a path that bends at this node
return 1 + max(l, r) # the parent can only descend one side
go(root)
return best
Maximum path sum is the same again, with values instead of counts and one extra rule — a branch with a negative total is worth not taking:
def max_path_sum(root):
best = float('-inf')
def go(node): # returns: best downward path from node
nonlocal best
if node is None:
return 0
l = max(go(node.left), 0) # clamp: skip a branch that costs you
r = max(go(node.right), 0)
best = max(best, node.val + l + r) # bends here, so both sides count
return node.val + max(l, r) # no bend, so pick one side
go(root)
return best
Line up the two lines that differ and the family is obvious:
| Problem | Returned upward | Recorded in best |
|---|---|---|
| Height | 1 + max(l, r) | — |
| Diameter | 1 + max(l, r) | l + r |
| Max path sum | val + max(l, r) | val + l + r |
The returned value uses one side; the recorded value uses both. That asymmetry is not a detail, it is the invariant. A path that goes up through the parent enters this node from above and leaves down one branch — it cannot use both. A path that bends at this node uses both and then stops, which is why it can only ever be recorded, never returned.
Return l + r instead and the parent builds a "path" that enters the child's
left branch, comes back through the child, and leaves down its right branch,
visiting the child twice. On a tree where the answer is a straight line down one
side, the symmetric test cases still pass, so this bug survives casual checking.
Say the two roles aloud before you write the function: returns the best
downward path, records the best bent path.
All three are O(n) time, one visit per node, with O(h) stack. Touching 10⁶ nodes means 10⁶ pointer dereferences into scattered heap addresses at roughly 100 ns each — about 0.1 s of memory latency, before any arithmetic. The traversal is never the thing to optimise; the number of traversals is.
Rebuilding a tree from two traversals
Preorder plus inorder determines the tree, and the argument is two sentences. Preorder's first element is the root. Find it in inorder at index i: everything before i is the left subtree and everything after is the right, so the left has i nodes and preorder's next i elements are exactly its preorder. Recurse on both halves.
def build(preorder, inorder):
pos = {v: i for i, v in enumerate(inorder)} # value -> index, built once
it = iter(preorder)
def go(lo, hi): # inorder window [lo, hi)
if lo >= hi:
return None
val = next(it)
i = pos[val]
node = Node(val)
node.left = go(lo, i) # must run before the right
node.right = go(i + 1, hi)
return node
return go(0, len(inorder))
The index map is the difference between a passing solution and a slow one. Scanning inorder for the root costs O(n) per node, so the naive version is O(n²): at n = 10⁴ that is 10⁸ steps, ten seconds or so in Python, against 10⁴ steps with the map. Building the map costs one pass and one dictionary. Its precondition is distinct values — with duplicates, the root's position in inorder is ambiguous and no reconstruction is well defined.
Postorder plus inorder works the same way, reading the root from the end.
Preorder plus postorder does not determine the tree. The smallest counterexample is two nodes: a root 1 with a left child 2, and a root 1 with a right child 2, both give preorder 1 2 and postorder 2 1. Preorder pins the root at the front and postorder pins it at the back; neither says which side the single child hangs on. The ambiguity is exactly the nodes with one child, which is why the pair does determine a full binary tree, where every node has zero children or two — there, preorder's second element must be the left child's root, and finding it in postorder sizes the left block.
In an interview
Open with the two roles before the code. "This is a postorder walk. Each call returns the best path going down from this node, and records the best path that bends at it." An interviewer who hears that sentence knows you understand the problem, and the twenty lines after it are then just typing.
When you are asked for diameter after height, say the code is the same with one added line rather than starting a fresh function. Recognising a shape you have already used is what the "find the waste" step of the solving loop is for, and it generalises to the ordering problems in the BST invariant.
The mistake that loses points: returning the recorded value. It is the single most common tree bug, it survives symmetric test cases, and the fix is a sentence you should have said before writing the line.
Check yourself
In maximum path sum, why is the returned value val + max(l, r) rather than
val + l + r, when the recorded value is the latter?
A parent extends the path down through this node and out one branch, so it can use at most one side. Returning both sides would let an ancestor build a path that visits this node twice, which is not a path.
You reconstruct a tree from preorder and inorder by scanning inorder for each root. n is 10⁴. Estimate the cost and the fix.
O(n) scan per node gives O(n²) ≈ 10⁸ steps, on the order of ten seconds in Python. A value-to-index dictionary built in one pass makes each lookup O(1), so the whole build is about 10⁴ steps.
Someone hands you preorder and postorder and asks for the tree. What do you ask them first?
Whether every node has zero or two children. For a full binary tree the pair is enough; otherwise a node with one child is ambiguous — root 1 with left child 2 and root 1 with right child 2 produce identical preorder and postorder.