Diameter of Binary Tree: Global Max with Local Returns

You are given the root of a binary tree. Return the length of the diameter, which is the longest path between any two nodes. The path does not need to pass through the root.

This is LeetCode 543: Diameter of Binary Tree, and it is the problem that teaches you one of the most useful tricks in tree recursion: returning one thing to your parent while updating a different thing globally. Once you learn this trick, you can apply it to dozens of other tree problems.

Why this problem matters

If you have already solved Maximum Depth of Binary Tree, you know how to compute depth recursively. Diameter of Binary Tree takes that same depth logic and adds a twist. The answer is not just the depth. The answer is the longest path through some node, and that path is left_depth + right_depth at that node.

The catch is that the longest path might not pass through the root. It could be entirely inside a subtree. So you cannot just compute the diameter at the root and call it a day. You need to check every single node and keep track of the best one you have seen.

This is where the global max with local return pattern comes in. Your recursive function returns depth (because the parent needs it), but it also updates a global variable with the diameter candidate at every node.

The key insight

At any given node, the longest path that passes through that node has two parts:

1. The deepest path going down through the left subtree
2. The deepest path going down through the right subtree

Add those two numbers together and you get the number of edges in the path through that node. That is the diameter at that node.

The overall diameter is the maximum of this value across all nodes in the tree.

But here is the subtle part. When you return a value to the parent, you cannot return left_depth + right_depth. That would mean your path forks at the current node and goes down both sides. Your parent cannot use a path that forks. It needs a single chain going straight down.

So you return 1 + max(left_depth, right_depth) to the parent (the depth of the deepest single path through this node), and you update the global max with left_depth + right_depth (the full diameter candidate through this node).

Two different values, two different purposes. That is the trick.

The solution

def diameter_of_binary_tree(root):
    diameter = 0

    def dfs(node):
        nonlocal diameter
        if node is None:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        diameter = max(diameter, left + right)
        return 1 + max(left, right)

    dfs(root)
    return diameter

Let's walk through each piece:

• diameter = 0 initializes the global max. Every node will try to beat this.
• if node is None: return 0 is the base case. A null node has depth 0. This is the recursive null base case pattern that shows up in every tree recursion.
• left = dfs(node.left) gets the depth of the left subtree.
• right = dfs(node.right) gets the depth of the right subtree.
• diameter = max(diameter, left + right) is the global update. The path through this node has left + right edges. If that beats the current best, update it.
• return 1 + max(left, right) is the local return. Tell the parent "the deepest single path through me has this many edges."

Visual walkthrough

Let's trace the recursion through the tree [1, 2, 3, 4, 5] step by step. At every node, pay attention to two numbers: what it returns to the parent (depth) and what it contributes to the global diameter (left + right).

The key moment is Step 4. At node 2, left_depth = 1 and right_depth = 1. The diameter candidate is 1 + 1 = 2. Then at the root (Step 6), left_depth = 2 and right_depth = 1. The diameter candidate is 2 + 1 = 3. That beats the previous best, so the global max updates to 3. That is our final answer.

Notice that the root is not special here. The root just happened to produce the best diameter candidate in this tree. In a different tree, the longest path might be entirely in a subtree and never touch the root. The algorithm handles that because it checks every single node.

Why you cannot just check the root

A common first instinct is to compute depth(root.left) + depth(root.right) and return that. That works for the example tree above, but it fails for trees where the longest path is buried in a subtree.

Consider this tree:

        1
       /
      2
     / \
    3   4
   /     \
  5       6

The diameter is 4 (path: 5 -> 3 -> 2 -> 4 -> 6), and it is entirely in the left subtree. The root's right child is null, so checking only at the root would give you 4 + 0 = 4, which happens to be correct here. But if you added a right child to the root, the root's diameter candidate would be 4 + 1 = 5, which would also be correct. The point is that you must check at every node because you cannot predict in advance which node will produce the maximum.

Complexity analysis

Time is O(n). Every node is visited exactly once. At each node we do O(1) work (a comparison and an addition).

Space is O(h) where h is the height of the tree. That is the depth of the recursion stack. For a balanced tree, h = log n. For a completely skewed tree, h = n.

No extra data structures needed. Just pure recursion plus one integer variable.

Edge cases to watch for

• Empty tree (root is None): return 0. The DFS is never called, and diameter stays at 0.
• Single node: return 0. Both children are null, so left + right = 0 + 0 = 0. The diameter is 0 edges.
• Straight line (skewed tree): the diameter equals n - 1 edges. The recursion handles it correctly.
• Diameter not through root: this is the whole point. The global max check at every node catches it.
• Balanced tree with diameter through root: left_depth + right_depth at the root will be the answer.

The building blocks

This problem is built on two fundamental building blocks:

1. Global max with local return (global-max-local-return). The recursive function returns one value (depth) to its caller, but also updates a separate global variable (diameter) at each node. The skeleton looks like this:

def solve(root):
    best = 0

    def dfs(node):
        nonlocal best
        if node is None:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        best = max(best, CANDIDATE(left, right))
        return LOCAL_RETURN(left, right)

    dfs(root)
    return best

For diameter of binary tree, CANDIDATE is left + right and LOCAL_RETURN is 1 + max(left, right). This pattern shows up in Binary Tree Maximum Path Sum (LeetCode 124) where the candidate includes node values, and in Longest Univalue Path (LeetCode 687) where the candidate depends on matching values. Same structure, different details.

2. Recursive null base case (recursive-null-base). The if node is None: return 0 base case terminates the recursion at leaves. This is the same pattern you see in Maximum Depth of Binary Tree, Invert Binary Tree, and essentially every recursive tree solution.

The combination of these two building blocks is what makes this problem click. You already know how to compute depth recursively (that is the null base case plus 1 + max(left, right)). The new thing is layering the global max on top: at every node, check left + right against the best you have seen.

From understanding to recall

You just read through a clean solution and traced through the recursion step by step. You understand why the function returns depth but tracks diameter globally. You understand why you check at every node instead of just the root. It all makes sense right now.

But when this problem comes up in an interview, will you remember that the function returns depth, not diameter? Will you remember that the global update is left + right while the return value is 1 + max(left, right)? Or will you mix them up and spend ten minutes debugging?

Understanding is not recall. You understood the solution. Recall means you can write it cold, under pressure, without second-guessing whether you should return left + right or 1 + max(left, right).

Spaced repetition builds recall. You practice typing the solution from scratch at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the global max update and the local depth return from memory. After a few repetitions, the pattern is automatic.

The global-max-local-return pattern and the recursive-null-base pattern are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Maximum Depth of Binary Tree - Uses the same depth recursion, but without the global max twist. Solve this one first if you have not already.
• Lowest Common Ancestor - Another post-order tree problem where the answer depends on information from both subtrees, but with a different aggregation strategy.