DP on Treestreeoptimization

Max Height of Tree when any Node can be Root

Given an undirected tree, for every possible choice of root node, find the height of the tree, the number of edges on its longest downward path to a leaf, when rooted at that node.

Do this lesson first: house robber

Example input

8 nodes; edges (0, 1), (0, 2), (0, 3), (1, 4), (1, 5), (3, 6), (4, 7)

Expected output

Heights with node 0 to node 7 as the root: 3, 3, 4, 4, 4, 4, 5, 5. The tallest is 5.

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

Root the tree at node 0, only to give every edge a direction; the answer is still computed for every root. Each node then holds three numbers. down[v] is the height of v's own subtree: the longest path that starts at v and only moves away from node 0. up[v] is the longest path that starts at v and leaves through its parent first, and it is 0 for node 0, which has no parent. height[v] is the height of the whole tree when v is the root, the number the problem asks for. Every path out of v starts either down into v's subtree or up through its parent, never both, so the two directions cover every path and height[v] is simply the larger.

down[v] = 1 + max over children c of down[c], 0 at a leaf; up[v] = max(1 + up[p], 2 + down[s] for each sibling s of v), where p is v's parent, 0 at the root; height[v] = max(down[v], up[v])

For down, the decision is which child the longest downward path steps into first: one edge to that child, then the best the child can do below it. For up, the first step is forced, to the parent p, and the decision is what happens at p: carry on the way p's own upward path does, which is up[p] plus the one edge, or turn down into a sibling's subtree, which is one edge to p, one edge to the sibling s, and down[s] below that. The path cannot turn back down into v's own subtree, because a path does not revisit v; that is why the sibling max leaves v out. That exclusion is the subtle step in rerooting: up[v] is exactly how tall p's side of the tree is when you look at it from v.

Bases: every leaf's down is 0, a path that goes nowhere, and up[0] is 0 because the root has no parent to leave through. down needs every child before its parent, so it fills from the leaves; with every parent numbered before its children, that is simply descending node order. up needs the parent's up before the child's, and the siblings' down, which the first pass has already finished, so it fills from the root out, in ascending order. height reads only its own node's two numbers, so it can go in any order once both passes are done. Two passes in opposite directions is the rerooting pattern: the first sees each subtree, the second sees everything else.

Tabulation over the tree, in two sweeps and a final combine. The naive alternative re-roots for real: a breadth-first search from every node, n searches of n steps each, O(n^2). The two sweeps touch each edge a constant number of times, apart from the sibling loop in the up sweep, which this page's code writes plainly as a loop over the parent's other children; on a star, one centre with n - 1 leaves, that loop alone is O(n^2). Keeping each parent's two tallest children removes it (see the variations), and then the whole method is O(n). Recursion is the more common way to write rerooting, one depth-first search for down and a second for up; the table's two sweep orders are those two searches made explicit.

Time O(n) with each parent's two tallest children kept; the plain sibling loop shown is O(n^2) on a starSpace O(n)

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

node 0

down3

up0

height3

node 1

down2

up3

height3

node 2

down0

up4

height4

node 3

down1

up4

height4

node 4

down1

up4

height4

node 5

down0

up4

height4

node 6

down0

up5

height5

node 7

down0

up5

height5

max-height-of-tree-any-node-root.ts

1function heightFromEveryRoot(parent) {
2 const n = parent.length;
3 const kids = Array.from({ length: n }, () => []);
4 for (let v = 1; v < n; v++) kids[parent[v]].push(v); // parent[v] < v
5 const down = new Array(n).fill(0), up = new Array(n).fill(0);
6 for (let v = n - 1; v >= 0; v--) // children before parents
7 for (const c of kids[v]) down[v] = Math.max(down[v], 1 + down[c]);
8 for (let v = 1; v < n; v++) { // parents before children
9 const p = parent[v];
10 up[v] = 1 + up[p];
11 for (const s of kids[p]) if (s !== v) up[v] = Math.max(up[v], 2 + down[s]);
12 }
13 const height = down.map((d, v) => Math.max(d, up[v]));
14 return height; // on this page's level-ordered tree, no node is deeper than n - 1, so it is a tallest root
15}

Base caseComputedBeing readAnswer

The code, the trap, the variations

max-height-of-tree-any-node-root.ts

1function heightFromEveryRoot(parent) {
2 const n = parent.length;
3 const kids = Array.from({ length: n }, () => []);
4 for (let v = 1; v < n; v++) kids[parent[v]].push(v); // parent[v] < v
5 const down = new Array(n).fill(0), up = new Array(n).fill(0);
6 for (let v = n - 1; v >= 0; v--) // children before parents
7 for (const c of kids[v]) down[v] = Math.max(down[v], 1 + down[c]);
8 for (let v = 1; v < n; v++) { // parents before children
9 const p = parent[v];
10 up[v] = 1 + up[p];
11 for (const s of kids[p]) if (s !== v) up[v] = Math.max(up[v], 2 + down[s]);
12 }
13 const height = down.map((d, v) => Math.max(d, up[v]));
14 return height; // on this page's level-ordered tree, no node is deeper than n - 1, so it is a tallest root
15}

Where people go wrong

Reading the parent's down value for the up step: up[v] = 1 + max(up[p], down[p]). down[p] is the tallest path below p, and that path can run back through v itself. Here down[0] = 3 is the path 0, 1, 4, 7, so the shortcut makes up[1] = 1 + 3 = 4, describing a 'path' 1, 0, 1, 4, 7 that crosses the edge between nodes 0 and 1 twice. The shortcut then gives height[1] = 4, when the farthest node from node 1 is only 3 edges away. Leaving v out of the max over p's children is the fix, and it is the reason up reads the siblings rather than down[p].

Keep each parent's two tallest children instead of looping over siblings.
The down pass also records, at each node, its two largest values of down[c] over its children c. up[v] then reads only one of them, besides up[p]: the larger one, unless it came from v itself, in which case the second (no second child means no sibling option). The passes and their order do not change, and the up pass drops to constant work per node, O(n) overall.
Give the edges weights.
Every 1 becomes the weight of the edge it counts: down[v] = max over children c of w(v, c) + down[c], and up[v] = max(w(v, p) + up[p], w(v, p) + w(p, s) + down[s] for each sibling s). With non-negative weights nothing else changes; the two passes and their order are the same.
Ask only for the tallest root, not every node's height.
That number is the tree's diameter, 5 here, and the down pass alone finds it: at each node add its two tallest child branches, 1 + down[c] each, counting a missing branch as 0, and take the largest such sum over all nodes. The up pass exists to give every node its own answer, which is the point of rerooting.
Sum the distances from every node to all the others (LeetCode 834).
Same two passes, with sums instead of maxes: the down pass also counts subtree sizes, and moving the root from p to a child c brings size[c] nodes one edge closer and pushes the other n - size[c] one edge further, so ans[c] = ans[p] - size[c] + (n - size[c]). No sibling exclusion is needed, because a sum, unlike a max, can subtract the child's share back out.

Longest repeating and non-overlapping substring