Diameter of Binary Tree
WHAT IT SAYS
Find the length in edges of the longest path between any two nodes in the tree — the path need not pass through the root.
WHAT IT'S REALLY ASKING
"Any path in a tree climbs for a while and then descends: it bends at exactly one topmost node. Stand at that node, and the path is just its left height glued to its right height. So the longest path anywhere is a question you can ask at every node — while you were computing heights anyway."
For every node, compute two heights and take the best
O(n log n) balanced, O(n^2) skewedThe longest path through a given node is height(left) + height(right). So loop over all nodes, call the height helper twice at each, and keep the maximum.
WHERE THE WORK IS WASTED — The same disease as the naive balance check, and worth diagnosing precisely: height() is called at every node, and each call re-walks the entire subtree beneath it. A node at depth d gets re-measured d times — once per ancestor — so the total work is the sum of all depths, quadratic on a spine. Every one of those repeat measurements returns the same number it returned last time. The recursion computes the answer and then discards it, forcing every ancestor to rediscover it by walking.
The longest path bends at exactly one highest node.
Take any path between two nodes in a tree. Because a tree has no cycles, the path has a unique node closest to the root — its apex. From the apex, the path descends into (at most) two different children and never climbs again: revisiting the apex would repeat a node. So every path in the tree is fully described as: an apex, plus a downward arm into its left subtree, plus a downward arm into its right subtree (either arm possibly empty). The longest path with apex v is therefore height(v.left) + height(v.right) — each arm maximised independently, which is legal because the two arms share no edges and cannot interfere. That gives a complete, non-overlapping classification: every path has exactly one apex, so checking the best path AT every node, as apex, covers all paths exactly once. The global diameter is the max over all nodes of that local sum. Now the fusion. The height recursion is already standing at every node in post-order, holding the left height and the right height in its hands. The apex question needs precisely those two numbers. So the answer to the diameter is a side effect: as heights flow upward, each node also computes leftH + rightH and offers it to a running maximum. Be exact about the two different quantities in flight, because conflating them is THE bug in this problem: the value RETURNED upward is 1 + max(leftH, rightH) — a path may only continue upward through one arm — while the value RECORDED is leftH + rightH, the bent path that ends here. Return the sum upward and you have invented paths that pass through a node twice.
Height recursion with a side channel
O(n) time, O(h) stack spaceOne post-order function: null returns 0; otherwise get both children's heights, update a running best with leftH + rightH, and return 1 + max(leftH, rightH). The diameter is the running best after the root's call finishes. If the problem counts nodes instead of edges, the answer is that best plus one.
Best Path Through Each Apex
YOU'LL SEE IT AGAIN WHEN
- The answer is a path between ANY two nodes, not root-to-leaf — so it bends, and the bend point is the natural place to measure it.
- Each candidate path has a unique topmost node, so per-node local answers cover the global space exactly once.
- The local answer combines both children (a sum), but the value passed upward may use only one child (a max) — two different quantities in one function.