Best path through each node
Each node returns its best single-branch; the answer considers both branches joined at the node.
The global best is updated with left + right + node, but only one side is returned upward.
01The intuition
Start with what you would do by hand
Take the tree with 1 at the top, 2 and 3 below it, and 4 and 5 below 2. The diameter is the longest path between any two nodes, counted in edges. By eye you can find it: 4 up to 2, up to 1, down to 3, which is 3 edges. By hand you would try every pair of nodes and count the edges between them. With 5 nodes that is 10 pairs. With n nodes it is about n2/2 pairs, and each count can take up to n steps: for 10,000 nodes that is roughly 500 billion steps. We need something that does not look at pairs at all.
Build the structure, one piece at a time
The tree is the only structure: a root, and every node with up to two children. The trick is to notice where the longest path "bends". Any path goes up for a while and then down. Its highest node is the bend. So the longest path is the longest left-going branch plus the longest right-going branch at some bend node. If we can compute, for each node, the length of the longest branch hanging below it, we can try every node as the bend.
Piece one: ask each node for its longest downward branch, in edges. A leaf has none: 0. A node with children returns 1 + the larger child branch. This is the post-order fold from recursive DFS.
Piece two: at every node, while we have both children's branch lengths in hand, also compute "left branch + right branch", the longest path that bends here. Keep the biggest of these in one shared variable, the running best.
Piece three, the subtle one: the node returns only one branch upward, the longer one, because a path that continues up to the parent can use only one side of this node. The bent path is recorded in the best variable and is never returned.
| Node | Left branch | Right branch | Bend here | Returns up | Best so far |
|---|---|---|---|---|---|
| 4 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 + 0 + 2 = 2 | 1 | 2 |
| 3 | 0 | 0 | 0 | 0 | 2 |
| 1 | 1 | 0 | 1 + 0 + 2 = 3 | 2 (unused) | 3 |
"Bend here" is the two branch lengths plus the two edges that connect the node to its children (when a child exists). The diameter is 3.
Why it is correct
Every path in a tree has exactly one highest node, so every path is counted as a "bend here" at that node. At that node the longest possible bent path uses the longest branch on each side, which is exactly what the children returned. So the maximum over all nodes of the bend value is the maximum over all paths.
best = max over v of ( branch(left(v)) + branch(right(v)) + edges to them )
Returning only the longer branch is also right: a path that goes through v and continues to v's parent enters v from above, so it can descend into only one of v's children. For maximum path sum with values that can be negative, the same shape works with one change: a branch that sums to less than 0 is replaced by 0, because it is better to not take it.
Why it is fast
Each node is visited once, does two additions and two comparisons, and returns one number. Total work: O(n). Compare with roughly n2 pairs by hand. The only extra memory is the recursion stack, O(h) where h is the height.
How to recognise it in an interview
Listen for "longest path", "path that need not pass through the root", or "best sum of a path between any two nodes". Say: "A path has a highest node. I will compute the best single branch below each node, and at each node combine the two branches into a candidate answer, returning only one branch upward." Diameter of Binary Tree is the pure form. Binary Tree Maximum Path Sum adds the rule that a negative branch counts as 0. Longest Univalue Path keeps a branch only if the child's value equals the node's.
02The idea in one line
Each node returns its best single-branch; the answer considers both branches joined at the node.
Reach for it when: Diameter, maximum path sum, longest univalue path.
Cost: O(n) time.
03The walk-through, step by step
The video works one example: Diameter of [1,2,3,4,5]. These are its captions in order, so you can follow without the video or check a step you missed.
- Each node returns its best single branch; the answer joins two branches at a node
- Recurse to the leaves first: 4 and 5 have no children
- Leaf 4 returns branch 0; leaf 5 returns 0
- Node 2: left 0, right 0 → path through it = 0 + 0 + 2 edges = 2
- Node 2 returns 1 + max(0, 0) = 1 upward
- Leaf 3 returns 0
- Root: left 1 + right 0 + 2 edges = 3 > 2, new best
- Root returns 1 + max(1, 0) = 2 (unused); the diameter is 3
- One post-order pass: O(n)
04Asked at Google
4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Binary Tree Maximum Path Sum | Hard | 47 | last 6 months |
| Diameter of Binary Tree | Easy | 44 | last 6 months |
| Longest Univalue Path | Medium | 17 | |
| Binary Tree Longest Consecutive Sequence II | Medium | 17 |
05Related patterns
Other patterns in Trees: Recursive DFS (post-order fold), Level-order BFS, Root-to-leaf path carry, Lowest common ancestor, Build from traversals, Iterative traversal with a stack, Column / coordinate traversal, Rerooting DP (sum over all roots), Post-order deletion / pruning, Tree as a graph (parent pointers), Tree DP: take or skip this node, Serialize / deserialize by BFS.