Tree Diameter

The diameter of a tree is the length of the longest path between any two of its nodes. (Length is measured in edges by default; specify “in nodes” if a problem wants that count instead.) Two algorithms are canonical: (a) two-pass BFS/DFS — pick any starting node, find the farthest node u from it, then find the farthest node v from u; the path from u to v is a diameter — works only on trees, not general graphs; and (b) single post-order DFS that, at every node, computes the height of its left and right subtrees and updates a global maximum with left_height + right_height. Both run in O(n) time. The single most common mistake is assuming the diameter must pass through the root — it usually does not.

1. Intuition — The Longest Walk Through a Castle

Think of a tree as a castle whose rooms (nodes) are connected by corridors (edges). The “diameter” is the longest hallway-walk you could possibly take inside the castle without ever revisiting a room — start at some room, walk through corridors, end at some other room, and the number of corridors you traversed is the path length. The diameter is the maximum length over all such walks.

This walk does not need to start or end at the castle’s main entrance (“the root”). It is perfectly possible — in fact common — for the longest walk to live entirely in one wing, never reaching the main hall. For example, in a tree where the root has two short branches and one branch with a deep tower, the longest walk is bottom-of-the-tower → up to the wing’s top → into another deep room — and the root might or might not be involved at all.

The two algorithms are two different ways of finding this longest walk. The two-pass BFS algorithm exploits a beautiful property: if you start anywhere and walk to the farthest room, that room is guaranteed to be one endpoint of some diameter — whatever that endpoint is, walking from it to the new farthest room gives the diameter itself. The post-order DFS algorithm thinks locally instead: at every room, the longest walk passing through that room equals the longest path going down its left wing plus the longest path going down its right wing. Compute that quantity for every room and take the maximum.

2. Tiny Worked Example

Consider the binary tree:

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

Heights (in edges, leaf = 0): 6 and 7 are leaves with height 0. 4’s height = 1 + height(6) = 1. 5’s height = 1 + height(7) = 1. 2’s height = 1 + max(height(4), height(5)) = 2. 3’s height = 0 (leaf). 1’s height = 1 + max(height(2), height(3)) = 3.

Now compute, at each node, “longest path passing through this node = left_height + right_height (using −1 for missing children, so left_height + 1 becomes 0 when there is no left child)”. A cleaner formulation that avoids the −1 bookkeeping: define down(v) = length of the longest downward path from v to a leaf, in edges. Then for each node v, the longest diameter-candidate passing through v is down(v.left) + 1 + down(v.right) + 1 = down(v.left) + down(v.right) + 2 (using down = -1 for null).

Walking through:

• At node 6 (leaf): down = 0. Through-path: −1 + −1 + 2 = 0. Just the node itself.
• At node 4: down(left=6) = 0, no right. Through-path: 0 + (−1) + 2 = 1 (one edge to leaf 6).
• At node 7 (leaf): down = 0. Through-path: 0.
• At node 5: down(right=7) = 0, no left. Through-path: (−1) + 0 + 2 = 1.
• At node 2: down(left=4) = 1, down(right=5) = 1. Through-path: 1 + 1 + 2 = 4. This is the longest path passing through node 2: 6 → 4 → 2 → 5 → 7, four edges.
• At node 3 (leaf): through-path = 0.
• At node 1 (root): down(left=2) = 2, down(right=3) = 0. Through-path: 2 + 0 + 2 = 4. (Path 6 → 4 → 2 → 1 → 3, also four edges.)

Maximum across all nodes = 4. The diameter is 4 edges. Note that the diameter passing through node 2 (6 → 4 → 2 → 5 → 7) does not pass through the root. This is the single most common bug source — see §6.1.

3. Algorithm A — Two-Pass BFS / DFS

Steps (textbook version, on an unrooted tree):

1. Pick any starting node s arbitrarily.
2. Run BFS (or DFS — either works) from s to find the node u farthest from s.
3. Run BFS again from u to find the node v farthest from u.
4. The path from u to v is a diameter. Its length is the diameter of the tree.

Why it works (proof sketch). The crucial lemma: the node u found in step 2 is guaranteed to be one endpoint of some diameter of the tree.

Consider any actual diameter (a, b) of the tree, and consider the path s → u. There is a unique simple path between any two nodes in a tree (no cycles), so the path from s to u either intersects the path from a to b or it does not. Either way, an exchange argument shows that the path from u to the farther of a, b is at least as long as the path from a to b — hence u is itself an endpoint of some diameter. The full proof is a careful case analysis; CP-Algorithms gives a clean version. Once we know u is a diameter endpoint, finding the farthest node from u traces out the whole diameter.

This algorithm only works on trees, not on general graphs.

The exchange-argument lemma above relies on uniqueness of the path between any two nodes — a property of trees. On a general graph (with cycles), the “farthest from farthest from arbitrary start” trick fails: the BFS from s finds a node that is far from s along some shortest path that may go around a cycle, and that node is not necessarily on a graph diameter. For weighted general graphs, finding the diameter requires all-pairs shortest paths (e.g., Floyd-Warshall in O(V³)).

Pseudocode:

diameter_two_bfs(tree):
    s := arbitrary node
    u := bfs_farthest(s)
    v, dist := bfs_farthest(u, return_distance=True)
    return dist

bfs_farthest(start):
    queue := [(start, 0)]
    visited := {start}
    farthest := start
    max_dist := 0
    while queue not empty:
        (node, d) := queue.popleft()
        if d > max_dist: max_dist, farthest := d, node
        for nb in neighbors(node):
            if nb not in visited:
                visited.add(nb)
                queue.append((nb, d + 1))
    return farthest, max_dist

O(n) time per BFS pass; two passes, so O(n) overall. O(n) space for the queue and visited set.

4. Algorithm B — Single-Pass Post-Order DFS

This is the algorithm overwhelmingly preferred on rooted binary trees (LC 543) because it requires no parent pointers, no explicit visited set, and no two-pass dance. It is the same general “compute via post-order recursion + update a global” pattern used in tree-DP problems generally.

Idea. For each node v, define down(v) = length of the longest downward path from v to a descendant leaf, in edges. The longest path passing through v is then down(v.left) + down(v.right) + 2 (or +1 for the missing edge if a child is null; cleanest with the convention down(null) = -1). The tree’s diameter is the maximum of this quantity over all nodes.

Pseudocode:

diameter_dfs(root):
    diameter := 0
    function down(node):
        if node is null: return -1
        l := down(node.left)
        r := down(node.right)
        diameter := max(diameter, l + r + 2)     # update global
        return 1 + max(l, r)                     # return downward height
    down(root)
    return diameter

Each recursive call does O(1) work outside the two recursive sub-calls; total work is O(n). Recursion-stack depth is O(h) where h is the tree’s height — O(log n) for balanced trees, O(n) for degenerate ones.

5. Python Implementation

Using the Node class from Tree Traversals:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def tree_diameter(root):
    """LC 543. Diameter measured in edges (NOT nodes)."""
    diameter = 0
    def height(node):
        nonlocal diameter
        if node is None:
            return 0  # height in edges of empty subtree, with the +1 absorbed below
        l = height(node.left)
        r = height(node.right)
        # Longest path through this node = l (down left) + r (down right)
        diameter = max(diameter, l + r)
        return 1 + max(l, r)  # height of this subtree
    height(root)
    return diameter

Note the bookkeeping convention: height(None) = 0 and height(leaf) = 1 (so “height” here is being used in the “number of edges from this node to deepest leaf in subtree, with empty = 0, leaf = 1” sense). At each non-null node, l + r already counts the edges from the node down both sides (one fewer than (l + 1) + (r + 1) = l + r + 2, because we add 1 to get from the node to its child but the child’s height already accounts for further descent). The result is correct as l + r because height returns “depth-in-edges + 1” — a small bookkeeping shift that matches the common LC 543 idiom.

If the problem asks for diameter in nodes instead of edges (some variants do), the answer is diameter_in_edges + 1.

For the unrooted / general-tree (adjacency-list) version of Algorithm A:

from collections import deque
 
def diameter_two_bfs(adj, n):
    """adj: adjacency list, n: number of nodes (0-indexed). Tree assumed (n-1 edges, connected)."""
    def bfs_farthest(start):
        dist = [-1] * n
        dist[start] = 0
        farthest = start
        q = deque([start])
        while q:
            u = q.popleft()
            if dist[u] > dist[farthest]:
                farthest = u
            for v in adj[u]:
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    q.append(v)
        return farthest, dist[farthest]
    u, _    = bfs_farthest(0)
    v, diam = bfs_farthest(u)
    return diam

6. Pitfalls

6.1 Assuming the Diameter Passes Through the Root

The single most common bug. The diameter is the longest path anywhere in the tree; it can lie entirely within one subtree, never touching the root. The §2 example demonstrates this — the diameter 6 → 4 → 2 → 5 → 7 does not include the root 1 (though there is a coincident diameter through the root in that example because of the tree’s specific shape; that’s coincidence, not necessity). Naive solutions that compute height(root.left) + height(root.right) give the longest root-passing path, which is generally smaller than the diameter. The fix is the global-update pattern in §4: compute the through-path at every node, not just the root.

6.2 Edges vs Nodes

LC 543 measures the diameter in edges. Some textbooks and contest problems measure it in nodes (which is edges + 1). Always confirm which units the problem wants. The +1/-1 confusion is a frequent off-by-one source.

6.3 Two-Pass BFS on Disconnected or Non-Tree Graphs

Algorithm A’s correctness proof assumes the input is a tree — connected, no cycles. On a forest (disconnected), each component has its own diameter; running the algorithm on a single component computes that component’s diameter only. On a graph with cycles, the algorithm is incorrect (see the warning in §3). Verify the input shape before reaching for two-pass BFS.

6.4 Recursion Depth on Deep Trees

Algorithm B is O(h) recursion stack, which is O(n) for a degenerate tree. Python’s default recursion limit (~1000) blows up for deeper trees. Either bump sys.setrecursionlimit or rewrite iteratively with an explicit stack.

6.5 Forgetting to Compare Through-Path at Every Node

A subtle variant of §6.1: code that recurses correctly but only updates the global at the root has the same bug. The diameter = max(diameter, l + r) line must execute on every node — that is, inside the recursion, not after.

6.6 Weighted Edges

The algorithms above assume unit-weight edges. For a tree with positive edge weights (often called the “weighted tree diameter”), Algorithm A still works if BFS is replaced with Dijkstra’s Algorithm or simple weighted DFS (BFS is wrong for weighted graphs even on trees). Algorithm B generalizes naturally: replace 1 + max(l, r) with weight_to_child + max(...) and l + r with l + r (now in weighted units).

For trees with negative edge weights, neither algorithm directly applies; you generally need all-pairs shortest paths.

6.7 The nonlocal/closure Trap in Python

Without the nonlocal diameter declaration, the inner height function would create a new local diameter on assignment and the outer one would never be updated. Equivalent traps in other languages: Java requires a single-element array (int[] diameter = {0}) because lambdas can only close over effectively-final variables; C++ requires capturing by reference ([&]).

7. Diagram — Diameter Through a Non-Root Node

flowchart TD
    R((1)) --> A((2))
    R --> B((3))
    A --> C((4))
    A --> D((5))
    C --> E((6))
    D --> F((7))

What this diagram shows. The tree from §2. Heights (edges to deepest descendant): node 6 = 0, node 7 = 0, node 4 = 1, node 5 = 1, node 3 = 0, node 2 = 2, node 1 = 3. Through-paths: at node 2, down_left + down_right = 1 + 1 = 2 plus the two edges from node 2 to its children, total 4 edges (path 6 → 4 → 2 → 5 → 7); at node 1, down_left + down_right = 2 + 0 = 2 plus the two edges, total 4 edges (path 6 → 4 → 2 → 1 → 3). Either path is a valid diameter; in this example two distinct diameters happen to share the same length. The key visual takeaway: the diameter is computed at the LCA of its two endpoints, which is not necessarily the root. In trees that are top-heavy or right-skewed, the diameter’s LCA can be deep inside the tree.

8. Variants and Generalizations

8.1 Diameter of an Unrooted Tree

The two-pass BFS algorithm works directly. The post-order DFS algorithm requires picking an arbitrary root first (any node works); the answer is invariant.

8.2 Diameter of a Weighted Tree

Replace BFS with weighted descent (DFS with edge-weight summation). The single-pass DFS variant generalizes: down(v) = max over children c of (weight(v,c) + down(c)); through-path at v = sum of the two largest weight(v,c) + down(c) values across v’s children (not just left + right — for general trees, a node can have arbitrarily many children, and the longest through-path uses the two largest down-extents).

8.3 Diameter of a General (Possibly K-ary) Tree

Same idea as weighted: at each node, find the top two largest “downward path lengths” among children, sum them, update global.

8.4 Tree Center

The center of a tree is the node (or pair of adjacent nodes) that minimizes the maximum distance to any other node. The center always lies on every diameter, at the middle. It can be found in O(n) by trimming leaves layer-by-layer until 1 or 2 nodes remain.

8.5 Tree Diameter on a Forest

Run the algorithm on each connected component; the forest’s “diameter” is typically defined as the maximum over per-component diameters.

8.6 Diameter of an Arbitrary Graph

For unweighted graphs, BFS from every vertex gives O(V·(V+E)); for dense weighted graphs, Floyd-Warshall gives O(V³). The two-pass BFS trick does not generalize beyond trees.

9. Complexity

Algorithm	Time	Space
Two-pass BFS (Algorithm A)	Θ(n)	Θ(n) (visited / dist arrays + queue)
Single-pass post-order DFS (Algorithm B)	Θ(n)	Θ(h) recursion stack

Both are optimal in the asymptotic sense — every node must be visited at least once to know its contribution to the diameter, hence Ω(n) lower bound.

In practice, Algorithm B is preferred for rooted binary trees (LC-style) because the recursion is short and clean and the constants are excellent. Algorithm A is preferred for unrooted trees stored as adjacency lists (typical of competitive programming problem statements) because it doesn’t require choosing a root.

10. Common Interview Problems

LC #	Problem	Notes
543	Diameter of Binary Tree	Canonical statement; in edges
124	Binary Tree Maximum Path Sum	”Diameter with weights” — values can be negative; sum the path
1245	Tree Diameter	General (k-ary) tree given as edge list
687	Longest Univalue Path	Diameter restricted to monochromatic edges
543 / 1522	N-ary tree diameter	Same idea, top-2 extents at each node
2246	Longest Path with Different Adjacent Characters	Top-2 extents pattern with a constraint

LC 124 (Binary Tree Maximum Path Sum) is essentially “weighted tree diameter where edges-and-nodes have values and any subset of the path can be skipped if it would make the sum smaller (clamp negative subpaths to 0).” Recognizing this generalization is a senior-level interview signal.

11. Open Questions

• Why is the two-pass BFS algorithm so under-taught compared to the single-pass DFS? It’s arguably more elegant on unrooted trees.
• Are there o(n) algorithms for diameter on certain restricted tree classes (caterpillar trees, balanced trees of known shape)? In general no, but compressed representations might allow it.
• What’s the cleanest weighted-tree diameter implementation that handles negative weights gracefully? Most exposition assumes non-negative weights.

12. See Also

• Binary Tree — underlying structure
• Tree Traversals — post-order is the recursion shape used here
• Depth-First Search — graph generalization
• Breadth-First Search — Algorithm A’s workhorse
• Lowest Common Ancestor — every diameter’s “midpoint” is the LCA of its two endpoints
• Floyd-Warshall — diameter of an arbitrary weighted graph
• Dijkstra’s Algorithm — weighted single-source shortest path (used in weighted-tree diameter)
• Big-O Notation
• SWE Interview Preparation MOC