You are given the root of a binary tree. Return its diameter: the length of the longest path between any two nodes, counted in edges. An edge is one link between a node and its child. The path does not have to pass through the root.
1 / \ 2 3 → 3 (the path 4 → 2 → 1 → 3 has three edges) / \4 5
Every path in a tree has a highest point, the node where the path stops going up and starts going down. For example, the path 4 → 2 → 1 → 3 goes up from 4 to 1, then down to 3. Its highest point is node 1.
Now fix a node X and ask: "what is the longest path whose highest point is X?" It goes as deep as possible into X's left side, and as deep as possible into its right side. Counted in edges, its length is:
\text{(depth of left subtree)} + \text{(depth of right subtree)}
Here "depth" means the number of nodes on the longest downward path, as in 4.14.2. A left subtree of depth 2 means 2 edges going down from X into it: one edge from X to its child, and one more inside.
So the real question is: try every node as the highest point, and keep the biggest left depth + right depth.
For every node, compute the depth of its left and right subtrees from scratch, using the function from 4.14.2.
python
def diameterOfBinaryTree(root): def depth(n): return 0 if not n else 1 + max(depth(n.left), depth(n.right)) def best(n): if not n: return 0 here = depth(n.left) + depth(n.right) return max(here, best(n.left), best(n.right)) return best(root)
Each call to depth walks a whole subtree. Doing that at every node walks the bottom nodes again and again, once for every node above them. For a tree shaped like a line, that is O(n^2).
The waste in one sentence: every node's depth is recomputed once for each of its ancestors, when one bottom-up pass could compute every depth exactly once.
Compute every node's depth in one pass, from the bottom up, exactly like 4.14.2. While you are standing at each node, with its left and right depths in hand, you already have everything needed for "the longest path whose highest point is here". So record that on the side, and keep the biggest.
Here is the part that trips people up, and it is the shape of many hard tree problems:
What the function returns is not what the problem asks for.
The function returns the depth, because that is what the node's parent needs. The diameter is stored in a separate variable, updated at every node.
Why two different numbers? Think about the parent. It wants to extend a path upward through this node. A path that continues upward can only come from one side of this node, so the parent only needs the deeper side: the depth. But the answer to the problem is allowed to turn around at this node and use both sides. Those are different numbers, so one is returned and the other is recorded.
Remember this sentence: return what the parent needs, record what the problem wants. It makes a whole family of tree problems routine, including 4.14.14 Binary Tree Maximum Path Sum, which is this exact shape with sums instead of lengths.
(1) The best path length found so far. It lives outside the recursive function, so every call can update it.
In Python, an inner function can read a variable from the outer function, but cannot reassign it. Writing best = ... inside depth would quietly create a new local variable. So we store it as self.best, an attribute of the object. (Declaring nonlocal best inside depth would also work.) In TypeScript, an inner function can update an outer let directly.
(2) A missing node has depth 0.
(3) Get the depths of both subtrees. Trust these calls.
(4) Record the longest path whose highest point is this node. That path goes down left edges on one side and right edges on the other, so its length is left + right. There is no + 1, because we are counting edges. If the problem counted nodes on the path, it would be left + right + 1. Check which one the problem wants before you write this line. Getting it wrong is the most common mistake here, and the two answers differ by exactly one.
(5) Return this node's depth to its parent. A path continuing upward can only use the deeper side, so 1 + max(left, right).
(6) Run the pass. We ignore what it returns, the root's depth. The answer is the recorded best.
The answer is 3, recorded at the root. Node 2 also recorded a candidate of 2 on the way. In a tree where the longest path does not pass through the root, one of those lower candidates wins instead. That is exactly why best is updated at every node, not only at the top.
Time. Each node is visited once, and each visit does constant work. So O(n).
Space. The waiting recursive calls form a chain as long as the tree's height, h. So O(h): about \log_2 n for a balanced tree, and n for a tree shaped like a line.
One node. Its depths are 0 and 0, so the diameter is 0. A single node has no edges.
A straight line of nodes. The longest path runs from top to bottom, through every node, and the answer is n - 1 edges.
The longest path avoids the root. For example, a root whose left child has two deep subtrees, while its right side is empty. The answer is recorded at that left child.
The same shape, return one thing and record another, covers a family.
Binary Tree Maximum Path Sum. Return the best downward sum, and record the best sum that turns at this node. See 4.14.14.
Longest Univalue Path. The same, but a path may only join nodes that hold equal values.
Balanced Binary Tree. Return the depth, and record whether the balance rule was ever broken. That is the next page, 4.14.4.
The general lesson: when the answer can turn around at a node but the parent can only use one side, return the one-sided value and record the two-sided one.
"Why does the function return depth, not diameter?" The parent can only extend a path through one side, so it needs the depth. The diameter uses both sides and cannot continue upward, so it is recorded on the side.
"Edges or nodes?" Edges here. Say which you are counting before you write line (4).
"Does the path have to go through the root?" No. That is exactly why every node is tried as the highest point.
One thing to volunteer: name the pattern out loud. "Return what the parent needs, record what the question wants." That sentence carries you through the two hard tree problems later in this chapter.