Patterns/Part II - Linked Structures/Tree Diameter

Pattern Reference

Tree Diameter

"Two BFS/DFS technique. Find longest path in any tree. Center(s) of tree."

Loading...

Deep Dive Tutorial

Tree diameter algorithm: (1) BFS from any node, find farthest node u. (2) BFS from u, find farthest node v. Distance uv = diameter. Why: the farthest node from any starting point is always an endpoint of some diameter. Rerooting: compute "down" distances (deepest path going into subtree) in first DFS, then "up" distances (going through parent and other subtrees) in second DFS. Each node's farthest neighbor is max(down, up).

Tree diameter and rerooting template
// Tree diameter via two BFS
function treeDiameter(n, edges) {
    const adj = Array.from({length: n}, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }

    const bfs = (start) => {
        const dist = new Array(n).fill(-1); dist[start] = 0;
        const q = [start]; let i = 0, farthest = start;
        while (i < q.length) {
            const u = q[i++];
            for (const v of adj[u]) if (dist[v] === -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
                if (dist[v] > dist[farthest]) farthest = v;
            }
        }
        return { farthest, dist };
    };

    const { farthest: u } = bfs(0);
    const { farthest: v, dist } = bfs(u);
    return { diameter: dist[v], endpoints: [u, v] };
}

// Rerooting: for each node, farthest distance in the whole tree
function allFarthest(n, adj) {
    const down = new Array(n).fill(0);   // farthest in subtree (rooted at 0)
    const down2 = new Array(n).fill(0);  // 2nd farthest (different subtree)
    const up = new Array(n).fill(0);     // farthest going through parent

    // DFS1: compute down[] (bottom-up)
    // DFS2: compute up[] (top-down), answer = max(down[u], up[u])
    // For each node: farthest = max(down[u], up[u])
}

Worked Problems

1
Tree Diameter
Medium
Solve ↗
2
All Nodes Distance K in Binary Tree
Medium
Solve ↗
3
Count Nodes Equal to Sum of Descendants
Medium
Solve ↗
4
Minimum Height Trees
Medium
Solve ↗
globe
Tree diameter proofs:
- Two BFS proof: farthest from any node is always a diameter endpoint
- Equivalently: if u is farthest from any node v, then u is an endpoint of some diameter

Tree center:
- 1 or 2 nodes equidistant from all leaves
- Found by peeling leaves (BFS from outside)
- OR: midpoint(s) of diameter path

Rerooting DP pattern:
1. DFS1 (bottom-up): compute dp[v] for subtree rooted at v
2. DFS2 (top-down): compute dp2[v] = contribution from parent side
3. Answer at v = combine dp[v] and dp2[v]

Used for: sum of distances (each node as root), max path through each node, count of nodes at each distance.
← All Patterns