Re-rooting Technique
Compute the answer with one root, then efficiently shift the root to each neighbor in O(1) using the relationship between parent and child answers. Solves 'find the best root' in O(n) instead of O(n²).
How It Works
Re-rooting (the 'DP on trees, all roots' technique) answers a per-root question — like the sum of distances from every node to all others — without rerunning an O(n) DFS from each of the n roots. A first post-order pass computes each node's answer restricted to its own subtree, along with helper aggregates such as subtree sizes. A second pre-order pass then transfers the answer from parent to child in O(1): when the root shifts across an edge, the child's subtree gets one step closer while everything else gets one step farther, e.g. ans[child] = ans[parent] + (n - size[child]) - size[child].
Two linear traversals replace n independent ones, cutting O(n^2) to O(n). The method applies whenever a root's answer decomposes into contributions from inside and outside each subtree.
Step-by-Step Visualization
Code
static int[] sumOfDistancesInTree(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int[] e : edges) { graph.get(e[0]).add(e[1]); graph.get(e[1]).add(e[0]); }
int[] count = new int[n], dist = new int[n];
Arrays.fill(count, 1);
dfs1(graph, 0, -1, count, dist);
dfs2(graph, 0, -1, count, dist, n);
return dist;
}
static void dfs1(List<List<Integer>> g, int node, int parent, int[] count, int[] dist) {
for (int child : g.get(node)) {
if (child != parent) {
dfs1(g, child, node, count, dist);
count[node] += count[child];
dist[node] += dist[child] + count[child];
}
}
}
static void dfs2(List<List<Integer>> g, int node, int parent, int[] count, int[] dist, int n) {
for (int child : g.get(node)) {
if (child != parent) {
dist[child] = dist[node] - count[child] + (n - count[child]);
dfs2(g, child, node, count, dist, n);
}
}
}Tips & Gotchas
Practice Problems
- 1Sum of Distances in Tree
- 2Minimum Height Trees
- 3Count Number of Possible Root Nodes
- 4Maximum Number of K-Divisible Components
About the Tree DP Pattern
Run DP on a tree where each node's answer depends on its children's answers. Process leaves first (base cases), then compute internal nodes bottom-up. The DFS naturally handles the ordering.
The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.
Common Dynamic Programming Interview Problems
- Climbing Stairs
- Coin Change
- Longest Common Subsequence
- 0/1 Knapsack
- Edit Distance
- House Robber
- Longest Increasing Subsequence
- Word Break
Frequently Asked Questions
When should re-rooting come to mind?
Whenever a problem asks for a value computed 'for every node as the root' — total distances, farthest leaf, best orientation — and one rooted DFS already solves it for a single root. If shifting the root across one edge changes the answer by a formula involving subtree aggregates, re-rooting applies.
Why are two passes necessary instead of one?
The first (post-order) pass can only see information below each node, but the true answer also depends on the part of the tree above it. The second (pre-order) pass pushes that 'above' contribution downward, since the parent's completed answer encodes everything outside the child's subtree.
What is the most common mistake when deriving the transfer formula?
Forgetting to remove the child's own contribution from the parent's answer before adding the 'rest of the tree' term, which double-counts the child's subtree. Deriving the formula on a three-node example and checking it by brute force catches this quickly.