LeetCode 543 · Trees

Diameter of Binary Tree, explained with a picture

The longest walk between two leaves.

EasyTrees
▶ Watch it step by step

The problem

The diameter of a binary tree is the number of edges on the longest path between any two nodes (the path does not have to pass through the root). Return it.

Input:  [1, 2, 3, 4, 5]
Output: 3   (path 4 → 2 → 1 → 3)

Picture it

Picture walking between two leaves of a tree. Any such walk goes up to some highest node and back down. So at every node, the longest walk that bends there is (depth of left side) + (depth of right side). We compute depths bottom-up and keep the biggest bend we’ve seen anywhere.

How to recognise it

  • The input is a binary tree and the question is about the longest path between any two nodes.
  • The path may bend at some node: up one side, through the node, down the other. It does not have to pass through the root.
  • Each node needs its children's heights, which a bottom-up depth-first search (DFS: follow one branch to the bottom before trying the next) already computes.
  • The answer counts edges, not nodes. Up to 10^4 nodes, so aim for one visit per node.

Start with brute force

Every path has one highest node where it bends. For each node, the longest path bending there is height(left) + height(right). Compute that at every node with a separate height function and keep the best.

def height(node):
    if not node:
        return 0
    return 1 + max(height(node.left), height(node.right))

def diameter_brute(root):
    if not root:
        return 0
    through = height(root.left) + height(root.right)
    return max(through, diameter_brute(root.left), diameter_brute(root.right))

Each height call walks a whole subtree, and every node is walked again for each of its ancestors. That is O(n log n) on a balanced tree and O(n²) on a chain: about 5 × 10^7 steps for 10^4 nodes.

From brute force to the idea

  1. Find the waste. Heights are recomputed from scratch at every ancestor, although a node's height never changes.
  2. Compute height once, bottom-up. A post-order DFS (children before the node) gets l and r, the heights of the two subtrees, and returns 1 + max(l, r) to its parent.
  3. Record the bend on the way. While l and r are in hand, l + r is the number of edges on the longest path bending at this node: l edges down the left, r down the right. Keep the largest in best.
  4. Return one thing, record another. The function returns a height (a path that can still be extended upwards) but records a diameter (a path that bends and cannot). nonlocal best lets the inner function update the outer variable.

This is the key idea: one DFS returns heights, and at each node l + r is a candidate answer.

The key idea

One DFS returning height; at each node update best = max(best, leftHeight + rightHeight). O(n).

Python solution

def diameter(root):
    best = 0
    def depth(node):
        nonlocal best
        if not node:
            return 0
        l, r = depth(node.left), depth(node.right)
        best = max(best, l + r)          # path that bends at this node
        return 1 + max(l, r)
    depth(root)
    return best

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n log n) balanced, O(n²) chain: heights recomputed for every ancestorO(h): recursion only, h is the height
One DFS (shown code)O(n): each node visited once, O(1) workO(h): one stack frame per level, h = n for a chain

Edge cases

  • Single node: returns 0 (no edges).
  • Two nodes: returns 1.
  • Empty tree: returns 0, though LeetCode guarantees at least one node.
  • Longest path avoids the root ([1, 2, null, 3, 4, 5, null, 6]): returns 4 (6 → 4 → 2 → 3 → 5); the root contributes only 3.
  • Chain of n nodes: returns n − 1.
  • Very deep tree: a chain of about 1,000 nodes hits Python's default recursion limit (RecursionError); LeetCode allows 10^4 nodes. Use an explicit stack if that matters.

Common mistakes

  • Returning height(root.left) + height(root.right) only, which assumes the path passes through the root.
  • Returning l + r from the recursion: a parent cannot extend a path that already bends.
  • Counting nodes instead of edges, which is off by one.
  • Forgetting nonlocal, so best = max(...) raises UnboundLocalError.
Your turn: longest same-value path

Return the number of edges on the longest path where every node has the same value (LeetCode 687). For [5, 4, 5, 1, 1, null, 5] the answer is 2 (the three 5s). Describe your approach, then write it if you like.

Compare with our answer

Same shape, but an arm only continues into a child with the same value. Each call returns the longest same-value arm going down from the node; at each node, the two arms added together are a candidate.

def longest_univalue_path(root):
    best = 0
    def arm(node):
        nonlocal best
        if not node:
            return 0
        l, r = arm(node.left), arm(node.right)
        l = l + 1 if node.left and node.left.val == node.val else 0
        r = r + 1 if node.right and node.right.val == node.val else 0
        best = max(best, l + r)
        return max(l, r)
    arm(root)
    return best

Time O(n), space O(h).

A strong answer mentions: always recursing into both children (a mismatched child may still hold a long path), cutting the arm to 0 on a mismatch, and recording l + r while returning max(l, r).

Check what stuck

1. In a tree of cities joined by roads (no cycles), you must find the two cities farthest apart. Which approach fits best?

2. Why does the shown function return 1 + max(l, r) but record l + r?

3. A learner returns height(root.left) + height(root.right) as the diameter. Which tree is now answered wrongly?

Score 60% or more and the lesson is marked complete.