Diameter of Binary Tree

This problem teaches the most reusable idea in tree interviews: return one value, record another. The quantity the question asks for — the longest path — is not the quantity a parent can use. Once you see that split, Balanced Binary Tree, Binary Tree Maximum Path Sum and a dozen other problems become the same function with a different line in the middle.

It is rated easy, but many candidates first write a version that is correct and quadratic. The interviewer's follow-up is then "what is the complexity on a skewed tree?", and the honest answer is the start of the real solution.

The problem

Given the root of a binary tree, return the length of the longest path between any two nodes, measured in edges. The path does not have to pass through the root.

            1          /   \         2     3       /   \      4     5     /       \    6         7   /           \  8             9

• For this tree the answer is 6: the path 8 – 6 – 4 – 2 – 5 – 7 – 9 has six edges. The best path through the root, 8 – 6 – 4 – 2 – 1 – 3, has only five.
• For a single node the answer is 0: there is no edge.

Constraints: 1 ≤ n ≤ 10⁴ nodes, and the tree may be very unbalanced.

Clarifying questions

• Edges or nodes? Edges. (A path of k nodes has k − 1 edges; getting this wrong gives an off-by-one on every answer.)
• Must the path go through the root? No — and the example above is chosen so that it does not.
• Does the path have to go downward? No. It can go up from one node to a common ancestor and down to another, but it cannot visit a node twice.
• Empty tree? The constraints say at least one node; return 0 for an empty tree anyway.

Approach 1: the simple way

Every path has one highest node — the point where it "bends". The longest path bending at a node goes down as far as possible on the left and as far as possible on the right. So: for every node, compute the height of its left subtree and its right subtree, add them, and keep the best.

1def height(node: Optional[TreeNode]) -> int:2    """Nodes on the longest downward path from node."""3    if node is None:4        return 05    return 1 + max(height(node.left), height(node.right))678def diameter_brute(root: Optional[TreeNode]) -> int:9    """Try every node as the bend; recompute heights each time."""10    if root is None:11        return 012    through_here = height(root.left) + height(root.right)13    return max(through_here, diameter_brute(root.left), diameter_brute(root.right))

Here height counts nodes, so height(left) + height(right) counts exactly the edges of the bent path: each node on the left arm contributes the edge above it, and so does each node on the right arm.

It is correct. The cost is the problem. Each call to height walks the whole subtree below it, and diameter_brute calls it at every node. On a balanced tree, each node is re-walked once per ancestor, so O(n log n). On a chain, the subtree sizes are n − 1, n − 2, … — about n²/2 steps. A chain of 1,000 nodes makes over 1,000,000 calls to height; at the full 10⁴ it is on the order of 10⁸. Too slow, and it also recurses 10⁴ deep.

The key insight

The brute force computes every height many times. But a single postorder walk already produces every height once: height(node) = 1 + max(height(left), height(right)). At the moment a node has its two children's heights in hand, it also has everything needed for the path bending at it: left + right.

So do both in the same call — but notice they go to different places:

• The height goes up to the parent. A parent can extend a straight path down through this node, so it needs 1 + max(left, right).
• The bend is recorded on the side. A parent cannot extend a path that already goes down the left and back up the right; that path is finished. So left + right is compared against a best-so-far variable and never returned.

That split is the whole lesson. The value the question asks for is not what the recursion returns.

Approach 2: one pass, return the height, record the bend

1def diameter(root: Optional[TreeNode]) -> int:2    """Edges on the longest path between any two nodes."""3    best = 045    def depth(node: Optional[TreeNode]) -> int:6        nonlocal best7        if node is None:8            return 09        left = depth(node.left)10        right = depth(node.right)11        best = max(best, left + right)    # the path that bends at this node12        return 1 + max(left, right)       # the straight path the parent can extend1314    depth(root)15    return best

nonlocal best lets the inner function update the outer variable. The alternative — returning a pair (height, best) from every call — works too, but it spreads the bookkeeping over every line.

Dry run on the example tree

Calls finish in postorder: 8, 6, 4, 9, 7, 5, 2, 3, 1.

The best, 6, is recorded at node 2 and never returned. The root only sees node 2's height, 4, and its own bend is 4 + 1 = 5. If the function returned the bend instead of recording it, the answer would be lost.

Complexity. Time is O(n): each node is visited once and does O(1) work. Space is O(h) for the recursion — O(log n) balanced, O(n) for a chain. For very deep trees, the same computation can be done with an explicit stack in postorder, storing each node's height in a dictionary.

Edge cases

• A single node. Both children return 0, the bend is 0, the answer is 0.
• A chain. A left-only chain of n nodes has diameter n − 1, recorded at the top node with left height n − 1 and right height 0.
• The answer is not at the root. The example tree. Any solution that only computes the bend at the root fails it.
• Empty tree. depth(None) returns 0 and best stays 0.

Saying it in the interview

Follow-ups

• "Is the tree height-balanced?" Same function: return the height, but return −1 as soon as any node's children differ by more than 1, and pass −1 straight up. O(n) instead of the O(n²) "call height at every node" version.
• "Longest path where every node has the same value." Same shape: a child's arm counts only if its value matches the parent's; record the bend, return the longer matching arm.
• "The nodes have values; find the largest path sum." Binary Tree Maximum Path Sum, the last lesson of this section: the same return/record split, plus dropping negative arms.