Pattern Guide
Tree Diameter & Path Queries
"Diameter via two BFS. Rerooting DP for all-root path queries. Longest path in O(n)."
The tree diameter is the longest path between any two nodes. Found via two BFS/DFS: first from any node to find the farthest node u, then from u to find the farthest node v — distance uv is the diameter. Rerooting DP computes the longest path through each node as root in O(n) using a two-pass DFS. Essential for: farthest node from each node, tree center, and path queries on trees.
Problems you can solve with this pattern
4 problems · click any to start solving
// 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])
}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 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])
}- 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.