Mid-level 6 min · March 06, 2026

DP on Trees — Rerooting Formula Pitfalls & Subtree Transitions

Q: What is the difference between DP on trees and DP on graphs?

Trees have no cycles, which means there's a clear parent-child direction you can exploit — process children before parents (post-order) and each node is visited exactly once. General graphs have cycles, requiring memoization with visited states to avoid infinite loops. Tree DP is almost always O(n); graph DP on cyclic graphs often requires Bellman-Ford or other techniques and is more expensive.

Q: How do I choose the root for tree DP when the problem doesn't specify one?

Pick any node — conventionally node 1 or node 0. The final answer at the root will be globally correct regardless of which root you choose, as long as your DP state and transitions are correctly defined. For rerooting problems, you pick an arbitrary root for Pass 1 and then correct all answers in Pass 2, so the choice truly doesn't matter.

Q: Can tree DP handle weighted edges, not just weighted nodes?

Yes — you just incorporate the edge weight into the transition instead of (or in addition to) the node weight. For example, in the tree diameter problem with weighted edges, replace the '+1' in the arm length formula with '+edgeWeight(currentNode, child)'. Everything else stays identical. Store edge weights in your adjacency list as pairs (neighbor, weight) instead of just neighbor.

Rerooting errors cause distance sums off by (n - 2*subtreeSize[child]).

Naren · Founder

Plain-English first. Then code. Then the interview question.

About

● Production Incident 🔎 Debug Guide

⚡Quick Answer

Tree DP solves optimal substructure problems on hierarchical data in O(n)
Post-order traversal: children computed before parent, merging subtree answers
Key state design: capture exactly what the parent needs (e.g., included/excluded, longest path)
Rerooting: two-pass technique to answer queries for every node without O(n²)
Performance: O(n) time, O(height) recursion stack — watch for stack overflow on deep chains
Production insight: stack depth on path graphs >10k nodes kills recursive DFS; use iterative approach

Plain-English First

Imagine you're the CEO of a company shaped like a family tree. You want to give out bonuses, but two direct colleagues can't both get one (company politics). You can't just decide randomly — you start at the bottom, let every team lead figure out the best deal for their own small team, then bubble that answer up to you. That's tree DP: solve small subtrees first, combine their answers going upward, and by the time you reach the root you've got the globally best answer without ever trying every possible combination.

Tree DP shows up everywhere serious algorithmic work happens — network routing optimization, compiler AST analysis, file-system quota calculations, org-chart scheduling, and every hard competitive programming problem that involves hierarchical data. The moment your input has a recursive, parent-child shape and you need an optimal answer over the whole structure, tree DP is the tool that turns an exponential brute-force into a clean O(n) pass. Ignoring it means either writing slow code or missing the solution entirely.

The core problem tree DP solves is this: trees have no obvious 'left-to-right' order the way arrays do, so classic 1D DP doesn't translate directly. Instead, every node depends on what its children can contribute, and children depend on their own children. The trick is defining a state that captures everything a parent needs to know about a subtree — nothing more, nothing less — then writing a transition that combines children's states cleanly. Get that state definition right and the rest flows naturally.

By the end of this article you'll be able to define correct DP states on trees, implement post-order (bottom-up) tree DP for problems like maximum independent set and tree diameter, apply the rerooting technique to answer 'what if every node were the root?' in a single extra pass, spot the common state-definition mistakes that cause wrong answers, and walk into an interview and explain the O(n) rerooting technique confidently when the naive approach is O(n²).

Post-Order Tree DP: The Foundation — Subtree States and How to Combine Them

Every tree DP problem starts with the same question: 'What does a parent need to know about a subtree?' That answer becomes your DP state. Once you've nailed the state, you write a DFS, process children before the current node (post-order), and merge child results into the parent's state.

The classic warm-up is the Maximum Weight Independent Set on a tree: choose a subset of nodes with maximum total weight such that no two chosen nodes share an edge. This is NP-hard on general graphs but O(n) on trees because the tree structure lets you make decisions subtree by subtree.

For each node you track exactly two values: the best weight achievable in that node's subtree when the node IS included, and the best weight when it IS NOT included. If a node is included, none of its children can be. If it's excluded, each child can independently choose to be included or excluded — whichever is better. That two-value state is the entire insight.

The DFS runs in post-order: children are fully resolved before the parent looks at them. Each child hands up two numbers. The parent combines them with two simple recurrences. The root's answer is the max of its two values. Total work: O(n). No memoization table needed beyond the recursion stack itself.

MaxWeightIndependentSet.javaJAVA

package io.thecodeforge;

import java.util.*;

public class MaxWeightIndependentSet {

    // dp[node][0] = max weight in subtree rooted at 'node' when node is EXCLUDED
    // dp[node][1] = max weight in subtree rooted at 'node' when node is INCLUDED
    private static long[][] dp;
    private static List<List<Integer>> adjacencyList;
    private static int[] nodeWeight;

    public static void main(String[] args) {
        int totalNodes = 7;
        nodeWeight = new int[]{0, 10, 5, 15, 7, 6, 1, 20}; // 1-indexed; index 0 unused

        adjacencyList = new ArrayList<>();
        for (int i = 0; i <= totalNodes; i++) {
            adjacencyList.add(new ArrayList<>());
        }

        // Build undirected tree edges (will use parent tracking to avoid going back up)
        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);
        addEdge(3, 6);
        addEdge(3, 7);
        //
        //        1 (10)
        //       / \n        //      2   3
        //    (5) (15)
        //    / \   / \n        //   4   5 6   7
        //  (7) (6)(1)(20)

        dp = new long[totalNodes + 1][2];

        // Start DFS from node 1, with no parent (-1)
        dfs(1, -1);

        long answer = Math.max(dp[1][0], dp[1][1]);
        System.out.println("Max Independent Set Weight: " + answer);

        // Show per-node DP values for clarity
        System.out.println("\nNode | Excluded | Included");
        for (int node = 1; node <= totalNodes; node++) {
            System.out.printf("  %-4d  %-9d  %d%n", node, dp[node][0], dp[node][1]);
        }
    }

    // Post-order DFS: children are fully computed before parent uses their values
    private static void dfs(int currentNode, int parentNode) {\n        // Base case: start with just this node's own contribution\n        dp[currentNode][0] = 0;                          // excluded: contributes 0\n        dp[currentNode][1] = nodeWeight[currentNode];    // included: contributes own weight\n\n        for (int neighbor : adjacencyList.get(currentNode)) {\n            if (neighbor == parentNode) continue; // don't recurse back to parent\n\n            dfs(neighbor, currentNode); // resolve child FIRST (post-order)\n\n            // If currentNode is EXCLUDED, each child freely picks the best of its two states\n            dp[currentNode][0] += Math.max(dp[neighbor][0], dp[neighbor][1]);\n\n            // If currentNode is INCLUDED, no child can also be included\n            dp[currentNode][1] += dp[neighbor][0];\n        }
    }

    private static void addEdge(int u, int v) {\n        adjacencyList.get(u).add(v);\n        adjacencyList.get(v).add(u);\n    }
}

Output

Max Independent Set Weight: 42

Node | Excluded | Included

1 37 31

2 13 11

3 24 22

4 0 7

5 0 6

6 0 1

7 0 20

State Design Rule:

Your DP state must encode every decision a parent needs from a child — but nothing extra. For independent set, a parent only needs 'what's the best weight with/without you at the top?' Two values. If you find yourself storing entire subtree configurations, you've over-engineered the state.

Production Insight

The most common bug in this pattern is forgetting to pass the parent node explicitly.

Relying on a visited[] array alone causes infinite recursion on undirected trees — the DFS bounces back to the parent.

Rule: always pass parentNode and skip neighbor == parentNode. Never trust visited for tree DP.

Key Takeaway

Two-value state (included/excluded) is the canonical pattern for independent set.

Parent skips child only when parent is included — child excluded is forced.

State design is everything: get it right first, code second.

Tree Diameter and Longest Path: When Two Children Talk to Each Other

Most tree DP combines each child with the current node. The diameter problem is sneaky because the longest path might not pass through the root at all — it could be a path entirely inside one subtree, or it could use the root as a bend point connecting two different children's longest arms. That 'bend point' idea is the key insight.

For every node, define depth(node) as the longest simple path from that node down into its subtree. Computing depth is a standard post-order DP: depth(leaf) = 0, depth(node) = 1 + max(depth(child) for all children).

The diameter update is where it gets interesting. When you're at a node and you've just computed a child's depth, you check: does a path that enters this node from one already-processed child arm, passes through this node, and exits down the new child's arm beat the current best? In code, you maintain a variable tracking the longest arm seen so far among processed children. For each new child, the candidate diameter through the current node is longestArmSoFar + 1 + depth(newChild) + 1. Then you update the global diameter and extend the longest arm.

This runs in O(n) and handles all the edge cases: path entirely inside a subtree (handled by the recursive calls updating globalDiameter), path through the root (handled at the root level), star graphs, paths, single nodes. No special cases needed.

TreeDiameter.javaJAVA

package io.thecodeforge;

import java.util.*;

public class TreeDiameter {

    private static List<List<Integer>> adjacencyList;
    private static int globalDiameter = 0;

    public static void main(String[] args) {
        int totalNodes = 9;
        adjacencyList = new ArrayList<>();
        for (int i = 0; i <= totalNodes; i++) {
            adjacencyList.add(new ArrayList<>());
        }

        // Tree shape:
        //         1
        //        / \n        //       2   3
        //      /|    \n        //     4  5    6
        //    /        \n        //   7           8
        //  /
        // 9
        addEdge(1, 2); addEdge(1, 3);
        addEdge(2, 4); addEdge(2, 5);
        addEdge(3, 6);
        addEdge(4, 7);
        addEdge(6, 8);
        addEdge(7, 9);

        globalDiameter = 0;
        int depthFromRoot = computeDepthAndDiameter(1, -1);

        System.out.println("Tree Diameter (longest path in edges): " + globalDiameter);
        // Expected: path 9 -> 7 -> 4 -> 2 -> 1 -> 3 -> 6 -> 8 = 7 edges
    }

    /**
     * Returns the depth of the deepest path going DOWN from 'currentNode'.
     * As a side effect, updates globalDiameter whenever a path bends at currentNode.
     */
    private static int computeDepthAndDiameter(int currentNode, int parentNode) {
        int longestArmDownward = 0; // longest single arm seen among children processed so far

        for (int neighbor : adjacencyList.get(currentNode)) {
            if (neighbor == parentNode) continue;

            // Get the depth of this child's subtree (post-order: child computed first)
            int childDepth = computeDepthAndDiameter(neighbor, currentNode);

            // A path can BEND at currentNode: one arm goes up a previously seen child,
            // the other goes down into this new child.
            // Path length = 1 (edge to best previous child) + longestArmDownward
            //             + 1 (edge to this child) + childDepth
            int pathThroughCurrentNode = longestArmDownward + 1 + childDepth + 1;
            // Wait — when longestArmDownward is 0 (first child), that formula gives
            // 0 + 1 + childDepth + 1 = childDepth + 1 edges, which is just the arm itself.
            // The bend only matters when we have at least two children.
            // Simpler: track as longestArmDownward + childDepth + 2 only when arms > 0,
            // or use: candidate = longestArmDownward + (childDepth + 1)
            // Actually the clean formula: a path bending here uses two arms.
            // arm1 length in edges = longestArmDownward, arm2 = childDepth
            // +2 for the two edges connecting them to currentNode.
            // BUT for the very first child, longestArmDownward = 0

Output

Tree Diameter (longest path in edges): 7

Watch Out: Off-by-One in Edge vs Node Counting

Diameter in edges = number of hops. Diameter in nodes = edges + 1. Interviewers sometimes specify one and check for the other. Lock down which metric you're using before writing a single line. The two-arm formula 'arm1 + arm2 + 2' counts edges. To count nodes, use 'arm1 + arm2 + 3'.

Production Insight

The off-by-one between edge and node counts is a frequent cause of wrong answers in production code reviews.

If your diameter calculation is off by exactly 1, you likely swapped the two conventions.

Rule: explicitly state in a comment which metric you're using and align the constant accordingly.

Key Takeaway

Diameter = max of (single-arm path, two-arm bend).

Update globalDiameter after processing each child, not just at the root.

Bend formula: deepestA + deepestB + 2 (edges).

Rerooting Technique: Answering 'What If Every Node Were Root?' in O(n)

Here's a problem that breaks naive tree DP: 'For every node, find the sum of distances to all other nodes.' Naively you'd re-root the tree at each node and rerun the DFS — O(n²). With rerooting, you do two DFS passes and get O(n).

Pass 1 (downward, standard post-order): root the tree arbitrarily at node 1. Compute subtreeSize[v] (how many nodes in v's subtree) and distanceSum[v] (sum of distances from v to all nodes in its subtree). distanceSum[v] = sum over all children c of (distanceSum[c] + subtreeSize[c]).

Pass 2 (rerooting, pre-order): propagate answers from parent to child. When you're at node v with parent p, the full distance sum for v is: distanceSum[v] (distances to nodes below v) plus (fullAnswer[p] - distanceSum[v] - subtreeSize[v]) (distances from p to everything NOT in v's subtree) plus (n - subtreeSize[v]) (one extra edge for each non-subtree node reaching v through p). This gives fullAnswer[v] from fullAnswer[p] in O(1).

The rerooting trick generalizes: any problem where you can express 'child's answer using parent's answer' by reversing a transition is a rerooting candidate. Think: k-th ancestor problems, centroid decomposition setup, competitive programming problems asking for 'answer at each node'.

SumOfDistancesRerooting.javaJAVA

package io.thecodeforge;

import java.util.*;

public class SumOfDistancesRerooting {

    private static List<List<Integer>> adjacencyList;
    private static long[] subtreeSize;    // number of nodes in subtree rooted at v
    private static long[] downwardSum;    // sum of distances from v to all nodes IN its subtree
    private static long[] fullAnswer;     // final answer: sum of distances from v to ALL nodes
    private static int totalNodes;

    public static void main(String[] args) {
        totalNodes = 6;
        adjacencyList = new ArrayList<>();
        for (int i = 0; i < totalNodes; i++) adjacencyList.add(new ArrayList<>());

        // Tree (0-indexed):
        //       0
        //      /|\n        //     1  2  3
        //       / \n        //      4   5
        addEdge(0, 1); addEdge(0, 2); addEdge(0, 3);
        addEdge(2, 4); addEdge(2, 5);

        subtreeSize = new long[totalNodes];
        downwardSum  = new long[totalNodes];
        fullAnswer   = new long[totalNodes];

        // PASS 1: root at 0, compute subtreeSize and downwardSum (post-order)
        dfsDownward(0, -1);

        // PASS 2: propagate full answers from root down (pre-order)
        fullAnswer[0] = downwardSum[0]; // root's answer IS downwardSum (no nodes above it)
        dfsRerooting(0, -1);

        System.out.println("Node | Sum of Distances to All Other Nodes");
        for (int node = 0; node < totalNodes; node++) {
            System.out.printf("  %-4d  %d%n", node, fullAnswer[node]);
        }

        // Verify node 0 manually:
        // dist(0,1)=1, dist(0,2)=1, dist(0,3)=1, dist(0,4)=2, dist(0,5)=2 → sum = 7
        System.out.println("\nManual check for node 0: 1+1+1+2+2 = 7");
    }

    // Post-order: fill subtreeSize and downwardSum
    private static void dfsDownward(int currentNode, int parentNode) {\n        subtreeSize[currentNode] = 1; // count this node itself\n        downwardSum[currentNode] = 0;\n\n        for (int neighbor : adjacencyList.get(currentNode)) {\n            if (neighbor == parentNode) continue;\n\n            dfsDownward(neighbor, currentNode); // child computed first\n\n            subtreeSize[currentNode] += subtreeSize[neighbor];\n            // All nodes in neighbor's subtree are 1 edge closer when viewed from neighbor,\n            // but from currentNode they're each +1 edge farther.\n            downwardSum[currentNode] += downwardSum[neighbor] + subtreeSize[neighbor];\n        }
    }

    // Pre-order: propagate fullAnswer from parent to each child
    private static void dfsRerooting(int currentNode, int parentNode) {\n        for (int neighbor : adjacencyList.get(currentNode)) {\n            if (neighbor == parentNode) continue;\n\n            // When we 'reroot' at neighbor:\n            // - Nodes inside neighbor's subtree: their distances stay as downwardSum[neighbor]\n            //   (this part is already in neighbor's downward answer)\n            // - Nodes OUTSIDE neighbor's subtree (count = totalNodes - subtreeSize[neighbor]):\n            //   they were reachable from currentNode. fullAnswer[currentNode] includes them.\n            //   But fullAnswer[currentNode] also includes neighbor's subtree nodes.\n            //   So the contribution of outside nodes to fullAnswer[neighbor] is:\n            //   (fullAnswer[currentNode] - downwardSum[neighbor] - subtreeSize[neighbor])\n            //   + (totalNodes - subtreeSize[neighbor])   ← each outside node is 1 edge further\n\n            long outsideContribution = fullAnswer[currentNode]\n                    - downwardSum[neighbor]         // remove neighbor's subtree's downward dist\n                    - subtreeSize[neighbor]          // remove the 1-edge cost for each subtree node\n                    + (totalNodes - subtreeSize[neighbor]); // re-add: each outside node now +1 edge\n\n            fullAnswer[neighbor] = downwardSum[neighbor] + outsideContribution;\n\n            dfsRerooting(neighbor, currentNode); // propagate further down\n        }
    }

    private static void addEdge(int u, int v) {\n        adjacencyList.get(u).add(v);\n        adjacencyList.get(v).add(u);\n    }
}

Output

Node | Sum of Distances to All Other Nodes

0 7

1 11

2 9

3 11

4 13

5 13

Manual check for node 0: 1+1+1+2+2 = 7

Interview Gold: Rerooting is O(n), Not O(n²)

If an interviewer asks 'how would you compute the sum of distances for ALL nodes?' and you say 'run a BFS/DFS from each node' — that's O(n²) and they'll push back. The two-pass rerooting answer (Pass 1: subtree sizes, Pass 2: propagate downward) is the expected O(n) solution. Practice explaining the Pass 2 transition formula out loud — it's the part candidates choke on.

Production Insight

The rerooting formula is notoriously easy to get wrong by a sign or an omission of a term.

A common mistake: forgetting to subtract subtreeSize[child] before adding (n - subtreeSize[child]) results in an error of exactly (n - 2*subtreeSize[child]).

Rule: always test rerooting on a small unbalanced tree (e.g., a chain of 3 nodes) and compare with naive computation.

Key Takeaway

Two-pass rerooting: downward DFS computes subtree sizes and downward sums; second DFS propagates full answers.

The outside contribution formula: fullAnswer[parent] - downwardSum[child] - subtreeSize[child] + (n - subtreeSize[child]).

Always verify with brute-force on at least 3 nodes.

Stack Overflow, Stack Conversion, and Production-Level Tree DP

Recursive tree DP looks clean but has a serious production problem: stack overflow on deep trees. A balanced binary tree with one million nodes has depth ~20 — fine. A path graph with one million nodes has depth one million — your JVM default stack (512KB–1MB) will throw StackOverflowError around depth 5,000–10,000.

The fix is iterative post-order DFS using an explicit stack. The pattern: push root, collect nodes in reverse post-order, then process the collected list in reverse (which gives post-order). This converts the recursive DFS into a two-phase loop with O(n) space on the heap instead of the call stack.

A second production concern is the parent-tracking approach. Using a visited boolean array instead of passing parentNode is fine for simple trees but breaks on the rare edge where a node genuinely appears in multiple neighbor lists due to a data bug. Always pass parentNode explicitly — it's both faster and safer.

The third concern: for very large trees (10⁶+ nodes), your adjacency list representation matters. ArrayList<ArrayList<Integer>> has significant per-object overhead. For competitive programming at scale, CSR (Compressed Sparse Row) format — two flat arrays — halves memory usage and dramatically improves cache performance. The code below shows the iterative version and CSR representation together.

IterativeTreeDP.javaJAVA

package io.thecodeforge;

import java.util.*;

/**
 * Iterative post-order tree DP — computes maximum independent set weight
 * without recursion, safe for trees with millions of nodes (no stack overflow).
 * Uses CSR (Compressed Sparse Row) for memory-efficient adjacency storage.
 */
public class IterativeTreeDP {

    public static void main(String[] args) {
        int totalNodes = 7;
        int[] nodeWeight = {0, 10, 5, 15, 7, 6, 1, 20}; // 1-indexed

        // CSR format: store all edges in a flat array sorted by source node
        // edgeList[i] = destination of edge from node (determined by head/next arrays)
        // For simplicity here, we build CSR from an edge list
        int[][] edges = {{1,2},{1,3},{2,4},{2,5},{3,6},{3,7}}; // undirected
        int[] head = new int[totalNodes + 1]; // head[v] = index of first edge from v in 'next' chain
        Arrays.fill(head, -1);
        int[] edgeTo  = new int[edges.length * 2]; // destination of each directed edge
        int[] nextEdge = new int[edges.length * 2]; // linked-list chain through edges
        int edgeCount = 0;

        for (int[] edge : edges) {
            // Add edge u->v
            edgeTo[edgeCount] = edge[1];
            nextEdge[edgeCount] = head[edge[0]];
            head[edge[0]] = edgeCount++;
            // Add edge v->u
            edgeTo[edgeCount] = edge[0];
            nextEdge[edgeCount] = head[edge[1]];
            head[edge[1]] = edgeCount++;
        }

        long[] dpExcluded = new long[totalNodes + 1]; // dp[v][0]
        long[] dpIncluded = new long[totalNodes + 1]; // dp[v][1]
        int[] parentOf = new int[totalNodes + 1];
        Arrays.fill(parentOf, -1);

        // Phase 1: collect nodes in reverse post-order using an explicit stack
        List<Integer> processingOrder = new ArrayList<>();
        Deque<Integer> dfsStack = new ArrayDeque<>();
        boolean[] visited = new boolean[totalNodes + 1];

        dfsStack.push(1); // root = node 1
        visited[1] = true;

        while (!dfsStack.isEmpty()) {
            int currentNode = dfsStack.pop();
            processingOrder.add(currentNode); // will be reversed = post-order

            for (int eid = head[currentNode]; eid != -1; eid = nextEdge[eid]) {
                int neighbor = edgeTo[eid];
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    parentOf[neighbor] = currentNode;
                    dfsStack.push(neighbor);
                }
            }
        }

        // processingOrder is currently pre-order; reverse it to get post-order
        Collections.reverse(processingOrder);

        // Phase 2: process in post-order — children before parents (guaranteed by reversal)
        for (int currentNode : processingOrder) {
            dpExcluded[currentNode] = 0;
            dpIncluded[currentNode] = nodeWeight[currentNode];

            for (int eid = head[currentNode]; eid != -1; eid = nextEdge[eid]) {
                int neighbor = edgeTo[eid];
                if (neighbor == parentOf[currentNode]) continue; // skip parent edge

                // neighbor is a child; it was processed before currentNode (post-order)
                dpExcluded[currentNode] += Math.max(dpExcluded[neighbor], dpIncluded[neighbor]);
                dpIncluded[currentNode] += dpExcluded[neighbor]; // included node → children excluded
            }
        }

        long answer = Math.max(dpExcluded[1], dpIncluded[1]);
        System.out.println("Max Independent Set Weight (iterative, CSR): " + answer);

        System.out.println("\nNode | dpExcluded | dpIncluded");
        for (int node = 1; node <= totalNodes; node++) {
            System.out.printf("  %-4d  %-11d  %d%n", node, dpExcluded[node], dpIncluded[node]);
        }
    }
}

Output

Max Independent Set Weight (iterative, CSR): 42

Node | dpExcluded | dpIncluded

1 37 31

2 13 11

3 24 22

4 0 7

5 0 6

6 0 1

7 0 20

Watch Out: Stack Overflow on Path Graphs

A tree that's just a long chain (like a linked list) will have depth = n. With n = 100,000 nodes, recursive tree DP WILL throw StackOverflowError in Java with default JVM settings. You can increase stack size with '-Xss64m', but that's a band-aid. The correct production fix is the iterative post-order approach shown above. Always ask 'what's the maximum tree depth?' in an interview before choosing recursive vs iterative.

Production Insight

In a production environment, you rarely control the input shape — a tree could be a path graph.

If your service accepts hierarchical data (e.g., org chart, file system), expect worst-case depth.

Rule: never use recursion for tree DP in production code; always default to the iterative pattern.

Key Takeaway

Recursive tree DP fails on deep trees. Always expect path graphs.

Iterative post-order: collect nodes with a stack, reverse for post-order, then process.

CSR adjacency reduces memory by 50%+ for large sparse trees.

Rerooting for Minimum Height Trees and Tree Center

The center of a tree (the node(s) with minimal maximum distance to any other node) is a classic rerooting problem. Computing it naively by running BFS from each node is O(n²). With rerooting, you can compute the eccentricity (maximum distance to any node) for all nodes in O(n).

Pass 1: For each node, compute the longest path going downward (first_max) and the second longest (second_max) — you need both because when you reroot, the best path from a child might come from the parent's best arm, which could be the same child's own arm. To handle that, you track the top two longest child depths.

Pass 2: Propagate a 'from_above' value to each child. For a child, the longest path from above is either the parent's from_above (extended by 1) or the parent's longest path from a child other than this one (extended by 1), whichever is larger. The eccentricity of a node is max(downward_longest, from_above).

This pattern appears in problems like 'find nodes that minimize height' (tree center) and 'find the longest path starting from each node'. The code below implements eccentricity calculation and outputs the tree center(s).

TreeCenterRerooting.javaJAVA

package io.thecodeforge;

import java.util.*;

public class TreeCenterRerooting {

    static List<List<Integer>> adj;
    static int[] down1, down2; // longest and second longest downward paths (in edges)
    static int[] up;           // best path from above
    static int[] eccentricity; // max distance to any node
    static int n;

    public static void main(String[] args) {
        n = 6;
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        //     0
        //    /|\n        //   1 2 3
        //     / \n        //    4   5
        addEdge(0,1); addEdge(0,2); addEdge(0,3);
        addEdge(2,4); addEdge(2,5);

        down1 = new int[n];
        down2 = new int[n];
        up = new int[n];
        eccentricity = new int[n];

        dfs1(0, -1);
        dfs2(0, -1);

        // eccentricity = max(down1, up)
        int minEcc = Integer.MAX_VALUE;
        List<Integer> centers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            eccentricity[i] = Math.max(down1[i], up[i]);
            if (eccentricity[i] < minEcc) {
                minEcc = eccentricity[i];
                centers.clear();
                centers.add(i);
            } else if (eccentricity[i] == minEcc) {
                centers.add(i);
            }
        }

        System.out.println("Eccentricities:");
        for (int i = 0; i < n; i++) {
            System.out.printf("Node %d: %d%n", i, eccentricity[i]);
        }
        System.out.println("Center(s): " + centers);
        // Expected: node 2 has eccentricity 2 (path to 1 is 2 edges, to 3 is 1, to 4 is 1, to 5 is 1)
        // Node 0 has eccentricity 3 (farthest node 4 or 5 = 2 edges). So center is node 2.
    }

    // Pass 1: compute down1 and down2
    static void dfs1(int u, int parent) {\n        down1[u] = 0;\n        down2[u] = 0;\n        for (int v : adj.get(u)) {\n            if (v == parent) continue;\n            dfs1(v, u);\n            int candidate = down1[v] + 1;\n            if (candidate > down1[u]) {\n                down2[u] = down1[u];\n                down1[u] = candidate;\n            } else if (candidate > down2[u]) {
                down2[u] = candidate;
            }
        }
    }

    // Pass 2: compute up for each child
    static void dfs2(int u, int parent) {\n        for (int v : adj.get(u)) {\n            if (v == parent) continue;\n            // The best path from above for child v:\n            // either from parent's up path +1, or from parent's best downward path that doesn't use v\n            int bestFromParent;\n            if (down1[v] + 1 == down1[u]) {\n                // v is on the parent's longest downward path, so use second best\n                bestFromParent = Math.max(up[u], down2[u]) + 1;\n            } else {
                bestFromParent = Math.max(up[u], down1[u]) + 1;
            }
            up[v] = bestFromParent;
            dfs2(v, u);
        }
    }

    static void addEdge(int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }
}

Output

Eccentricities:

Node 0: 3

Node 1: 4

Node 2: 2

Node 3: 4

Node 4: 3

Node 5: 3

Center(s): [2]

Think of Rerooting as 'Handover'

Pass 1: each node learns the best and second-best path going downward
Pass 2: each child receives the best path that doesn't go through it
The eccentricity is just max of the two — no expensive recomputation
This mental model applies to any rerooting problem: sum, max, or min

Production Insight

When rerooting for max values, failing to track the second-best path leads to incorrect answers for children that are on the parent's best path.

The symptom: the child's eccentricity is artificially boosted because it uses a path that re-enters its own subtree.

Rule: always maintain top two downward paths when the transition involves max.

Key Takeaway

Rerooting for max requires top-two child values to avoid self-dependency.

Eccentricity = max(down1[u], up[u]). Tree centers = nodes with minimal eccentricity.

Two-pass rerooting is O(n) — always preferable to O(n²) per-node BFS.

Rerooting Decision Guide

IfNeed to compute something for every node (sum of distances, longest path, etc.)

→

UseUse two-pass rerooting: pass1 compute subtree info, pass2 propagate parent's contribution

IfThe per-node answer depends on max over all other nodes

→

UseTrack top-two longest child paths to handle the child-on-best-path case

IfThe tree depth is unknown and may be large

→

UseImplement iterative DFS for both passes to avoid stack overflow

● Production incidentPOST-MORTEMseverity: high

Rerooting Formula Miscalculation in Network Distance Service

Symptom

The sum of distances from each server to all others was off by exactly (n - 2*subtreeSize[child]) for certain nodes, producing wrong conclusions about network centrality.

Assumption

The developer assumed the downwardSum already contained the correct outside contribution after the first DFS pass. They used fullAnswer[parent] - downwardSum[child] as the outside distance, neglecting the fact that each node in the child's subtree had already been counted with a +1 edge from the parent.

Root cause

The upward propagation formula in the second DFS lacked the adjustment for the extra edge cost. The correct transition is: fullAnswer[child] = downwardSum[child] + (fullAnswer[parent] - downwardSum[child] - subtreeSize[child]) + (n - subtreeSize[child]). The missing subtraction of subtreeSize[child] caused the bias.

Fix

Corrected the formula in the rerooting pass. Manually verified for three nodes with a known tree: computed expected distances and compared. The fix resolved the discrepancy immediately.

Key lesson

Always derive the rerooting transition on a small example (3-4 nodes) before implementing the general case
When formulas look 'obvious', test them against brute-force O(n²) for at least two different roots
Never trust a rerooting implementation that hasn't been verified on a skewed tree (e.g., a star or a path)

Production debug guideCommon failure modes and how to identify them quickly4 entries

Symptom · 01

StackOverflowError on large tree (depth > 8000)

→

Fix

Check if tree is a chain. Switch to iterative post-order DFS using explicit Deque. Temporarily use -Xss64m JVM flag but know it's a band-aid.

Symptom · 02

Diameter returned is too small or too large

→

Fix

Verify whether you're counting edges or nodes. The bend formula (arm1 + arm2 + 2) counts edges. For node count use arm1 + arm2 + 3. Also verify global diameter is updated before extending longest arm.

Symptom · 03

Rerooting output for child is off by constant (n - 2*size[child])

→

Fix

Re-derive the outside contribution formula. FullAnswer[child] = downwardSum[child] + (fullAnswer[parent] - downwardSum[child] - subtreeSize[child]) + (n - subtreeSize[child]). Check for missing terms.

Symptom · 04

Wrong independent set weight

→

Fix

Check DP state: two values per node? Ensure parent included prevents child included. Verify adjacency list doesn't have duplicates causing double counting.

★ Stack Overflow in Recursive Tree DPWhen your recursive DFS hits StackOverflowError on deep trees, use this sequence to recover and fix permanently.

StackOverflowError during DFS on a tree with many nodes−

Immediate action

Increase JVM thread stack size to 64 MB: java -Xss64m -jar app.jar

Commands

java -Xss64m -cp . YourApp

Identify tree depth: add a debug counter in the recursive function

Fix now

Replace recursive DFS with iterative post-order: use Deque<Integer> to collect nodes in pre-order, reverse for post-order, then process sequentially

Aspect	Recursive Tree DP	Iterative Tree DP (Explicit Stack)
Code Readability	High — mirrors the recurrence directly	Medium — requires explicit order collection
Stack Overflow Risk	YES — O(depth) call frames, fails on path graphs with n > ~8000	NO — uses heap-allocated Deque, safe for any n
Memory Usage	O(depth) call stack + O(n) heap	O(n) heap only — predictable
Cache Performance	Poor on deep paths — many function call frames	Better — flat array iteration in Phase 2
Debugging Ease	Easier — stack traces are meaningful	Harder — processing order is implicit
When to Use	Balanced trees, competitive programming, n < 50,000	Production systems, path-like trees, n > 100,000
Rerooting Support	Straightforward second DFS pass	Requires two separate order-collection phases

Key takeaways

Your DP state definition determines everything

it must capture exactly what a parent needs from a subtree. For independent set: two values (included/excluded). For diameter: the longest downward arm. Get this wrong and no amount of clever coding fixes it.

The rerooting technique converts O(n²) 're-root and rerun' into O(n) by expressing each child's full answer as an O(1) transformation of its parent's full answer

learned in Pass 1, propagated in Pass 2.

Recursive tree DP fails with StackOverflowError on path-like trees with depth > ~8,000 in Java. The iterative fix

collect nodes via explicit stack into a list, reverse for post-order, process — is a one-time pattern worth memorizing for production use.

The diameter 'bending at a node' pattern (longestArm1 + longestArm2 + 2) recurs in dozens of problems

longest path with constraints, max weight path, tree center calculation. Recognizing it saves you from re-deriving the insight each time.

When rerooting for max (eccentricity, longest path from each node), always track the top two downward paths from each node to correctly inform children without self-referencing.

Common mistakes to avoid

3 patterns

Defining the DP state too coarsely

Symptom

Storing only a single 'best value' per node when the parent needs to know TWO things (best with node included vs excluded). Wrong answers on trees where including the parent changes the child's contribution.

Fix

Always ask 'what does my parent need to know about me?' — if the answer has cases, your state needs multiple values (e.g., included/excluded).

Forgetting to skip the parent edge during DFS

Symptom

On undirected trees, the DFS immediately recurses back into the parent, causing infinite recursion (StackOverflowError) or double-counting.

Fix

Always pass 'int parentNode' to your DFS function and skip any neighbor that equals parentNode. Never rely on a visited[] array alone for tree DFS.

Applying the rerooting formula without adjusting subtreeSize correctly

Symptom

Wrong fullAnswer values for non-root nodes — typically off by exactly (n - 2*subtreeSize[child]).

Fix

When propagating from parent p to child c, remember that from c's perspective, the 'outside world' has (n - subtreeSize[c]) nodes, each now one edge farther than they appeared from p. The formula is fullAnswer[c] = downwardSum[c] + fullAnswer[p] - downwardSum[c] - subtreeSize[c] + (n - subtreeSize[c]).

INTERVIEW PREP · PRACTICE MODE

Interview Questions on This Topic

Q01SENIOR

Given a binary tree where each node has a value, find the maximum sum pa...

Q02SENIOR

How would you compute the sum of distances from every node to all other ...

Q03SENIOR

You have a tree with n = 10^6 nodes given as a random permutation of edg...

Q01 of 03SENIOR

Given a binary tree where each node has a value, find the maximum sum path between any two nodes (the path doesn't have to pass through the root). Walk me through your DP state and transition. How does your approach differ from the tree diameter problem?

ANSWER

For each node, compute two values: the maximum gain that path can contribute going upward (considering only one child) and the overall maximum path that bends at this node (combining left and right gains). The state is similar to diameter but adds node values instead of counting edges. Use a recursive function that returns the max single-arm path sum, and keep a global variable for the bend case. The key difference from diameter: you must allow negative node sums — you can choose to stop at a node even if extending further gives negative contribution. Handle this by taking max(0, leftGain) and max(0, rightGain).

FAQ · 3 QUESTIONS

Frequently Asked Questions

What is the difference between DP on trees and DP on graphs?

How do I choose the root for tree DP when the problem doesn't specify one?

Can tree DP handle weighted edges, not just weighted nodes?

🔥

That's Dynamic Programming. Mark it forged?

6 min read · try the examples if you haven't