Dynamic Programming • Trees

Diameter Based DP

Compute the longest path (diameter) between any two nodes in a tree using Post-Order Traversal.

Overview

Tree DP often involves computing a state for a node based on the states of its children. This is naturally done using a post-order traversal (DFS).

The height of a node is the length of the longest path from it down to a leaf. `height(u) = max(height(children)) + 1`.

The diameter path must "peak" at some node. The longest path peaking at node `u` is exactly the sum of the heights of its two tallest subtrees.

We compute the heights and update the global diameter simultaneously in one pass, avoiding repeated DFS calls.

0

1

2

3

4

Code Tracker

:::

1let diameter = 0;

2function dfs(u) {

3 let maxH1 = 0, maxH2 = 0;

4 for (let v of children[u]) {

5 let h = dfs(v);

6 if (h > maxH1) { maxH2 = maxH1; maxH1 = h; }

7 else if (h > maxH2) { maxH2 = h; }

8 }

9 diameter = Math.max(diameter, maxH1 + maxH2);

10 return maxH1 + 1;

11}

12dfs(root);