Diameter of Binary Tree

Diameter of Binary Tree is the problem that teaches you the post-order DFS trick: have a recursive call return one thing (the height) while quietly updating something else on the side (the best path). Once you see it, a whole family of tree problems falls open.

The slow way first

The brute-force idea: for every node, compute the height of its left subtree and the height of its right subtree, add them to get the longest path through that node, and take the max over all nodes. That is correct, but each height call walks a whole subtree, and we redo that work at every node — so it is O(n²) on a skewed tree.

The question to ask: can I get the height AND update the best path in the same pass? Yes — compute each height exactly once, and as the value bubbles up, fold it into a running maximum.

The idea: one DFS returns height, a side variable tracks the best

Do a single post-order DFS. For each node, recurse into both children first; they hand back left and right heights. The longest path through this node is left + right edges, so update a shared best. Then return this node height, max(left, right) + 1, to the parent.

The key insight: a node returns a height to its parent, but the answer lives in the side variable best, updated at every node. Heights compose; the diameter is just the largest left + right seen anywhere.

Walk through it

Step through the animation. DFS dives to leaf 4 first (height 1), then 5, then combines at node 2: left + right = 1 + 1 = 2, so best becomes 2. It visits leaf 3, then the root: left = 2, right = 1, so the path through the root is 3 — the new and final best. That winning path 4 - 2 - 1 - 3 lights up at the end.

Pseudocode

best = 0
define height(node):
    if node is None:
        return 0                       # empty subtree has height 0
    left  = height(node.left)          # recurse first (post-order)
    right = height(node.right)
    best = max(best, left + right)     # path THROUGH node, in edges
    return max(left, right) + 1        # height handed to the parent
call height(root)
return best

The Python solution

def diameter_of_binary_tree(root):
    best = 0
    def height(node):
        nonlocal best
        if node is None:
            return 0
        left = height(node.left)
        right = height(node.right)
        best = max(best, left + right)
        return max(left, right) + 1
    height(root)
    return best

• best is the answer, shared via nonlocal so the inner height can update it.
• The base case: an empty subtree (None) has height 0.
• We recurse into both children before doing anything — that is what makes it post-order.
• Line 9 is the heart: left + right is the longest path through this node, measured in edges, and we fold it into best.
• We return max(left, right) + 1 so the parent gets this node height — one more than its taller child.

Complexity

We visit every node once, so time is O(n). The extra space is the recursion stack, O(h) where h is the tree height — O(log n) for a balanced tree, O(n) for a skewed one.

When this pattern shows up

Practice