Mid-level 13 min · March 06, 2026

DP on Trees — Rerooting Formula Pitfalls & Subtree Transitions

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

N
Naren Founder & Principal Engineer

20+ years shipping performance-critical code where algorithms decide the bill. Notes here come from systems that actually shipped.

Follow
✓ Production
production tested
May 23, 2026
last updated
1,554
articles · all by Naren
 ● Production Incident 🔎 Debug Guide ⚙ Triage Commands
⚡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
✦ Definition~90s read
What is DP on Trees?

Tree DP is the art of solving problems on rooted trees by computing answers for subtrees bottom-up (post-order), then propagating results top-down to handle constraints that depend on the parent. The core insight: a naive O(n²) approach recomputes from scratch for every node, but two-pass DP achieves O(n) by first gathering subtree data (size, depth, diameter contributions) and then rerooting — adjusting formulas to shift the root and reuse computed states.

★
Imagine you're the CEO of a company shaped like a family tree.

This is essential for problems like tree diameter, maximum path sum, or minimum height trees, where the answer for each node depends on all others.

The critical pitfall lies in rerooting formulas: when moving a root from parent to child, you must correctly exclude the child's own subtree contribution from the parent's aggregated state, then recompute the child's new 'upward' contribution. A common mistake is double-counting or missing the case where the best path goes through the parent but uses the child's sibling — this requires tracking the top two values (e.g., longest and second-longest paths) per node.

In production, stack overflow from deep recursion (e.g., a 10⁵-node chain) forces conversion to iterative post-order using explicit stacks or BFS order arrays.

Real-world use: Facebook’s friend recommendation graph traversal, DNS zone delegation trees, and game AI decision trees all rely on this pattern. When not to use it: if the tree is dynamic (nodes added/removed) or you need approximate answers, consider centroid decomposition or heavy-light decomposition instead.

The rerooting technique specifically shines when you need O(1) per node after O(n) preprocessing — think 'answer for every node as root' problems like LeetCode 310 (Minimum Height Trees) or Codeforces 'Tree Painting'.

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²).

Why DP on Trees Requires Two Passes

Dynamic programming on trees is the technique of computing a function for every node by combining results from its children, then propagating those results upward. The core mechanic is a post-order traversal: for each node, you compute its DP value from the DP values of its children, typically in O(n) total time. The tree's acyclic structure guarantees that each node is processed exactly once after its subtree is fully resolved.

In practice, the critical property is that a single bottom-up pass gives you the answer for the root, but not for arbitrary nodes. To compute the DP value for every node, you need a second top-down pass — rerooting — that reuses the parent's computed value to adjust the child's result. This second pass is where most bugs live: you must correctly subtract the child's contribution from the parent's total before adding the parent's contribution to the child.

Use this pattern whenever the problem asks for a node-level metric that depends on the entire tree — for example, the farthest distance from each node (tree diameter per node), the sum of distances to all other nodes, or the maximum path sum starting at each node. It's the standard approach for problems like "Tree Distances" on CSES or "Sum of Distances in Tree" on LeetCode, and it directly models real systems like network latency analysis or hierarchical cost aggregation.

Rerooting ≠ Recomputing
Never recompute a child's DP from scratch during the second pass — that turns O(n) into O(n²). Always derive the child's value from the parent's already-computed result.
Production Insight
A team computed subtree sizes for a permission hierarchy but forgot to adjust the parent's count when rerooting, causing every non-root node to report incorrect user counts.
Symptom: root node was correct, but all other nodes showed off-by-one or off-by-subtree errors that grew with depth.
Rule: always subtract the child's contribution from the parent's total before adding the parent's adjusted contribution to the child.
Key Takeaway
DP on trees always requires two passes: bottom-up for subtree values, top-down for node-level answers.
Rerooting is O(n) only if you reuse parent results — never recompute from scratch.
The most common bug is forgetting to remove the child's contribution from the parent before passing the parent's value down.
DP on Trees: Rerooting & Subtree Transitions THECODEFORGE.IO DP on Trees: Rerooting & Subtree Transitions Two-pass DP technique for tree problems Post-Order DP: Subtree State Compute DP for each node from children up Tree Diameter: Combine Two Children Longest path via two deepest subtrees Rerooting Technique Recompute DP for each node as root Minimum Height Trees & Center Find root(s) minimizing tree height Stack Overflow Risk in Recursion Deep trees cause recursion depth errors ⚠ Recursion depth may overflow on deep trees Use iterative stack or increase recursion limit THECODEFORGE.IO
thecodeforge.io
DP on Trees: Rerooting & Subtree Transitions
Dynamic Programming Trees

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
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

Using Recursion — The Baseline That Ships to Prod (O(n) Time, O(h) Space)

Recursion is the idiomatic way to walk a tree. It maps directly to the problem: process children, combine results, return. The space complexity is O(h) where h is the height of the tree — that's the call stack. For a balanced tree, that's O(log n). For a degenerate tree (think linked list), it's O(n).

Most engineers stop there. They forget that the call stack is real memory. In production, hitting a stack overflow on a tree with 100k nodes is not a theoretical exercise — it's a P1 incident at 3 AM. The recursive solution works, but only if you know the shape of your data.

The code below solves "maximum root-to-leaf sum." It's textbook DP on trees: base case at null returns 0, recursive case adds the current node's value to the max of left and right subtrees. Simple. Deceptive. Production-ready only if your tree is small or balanced.

MaxRootToLeafSum.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// io.thecodeforge — dsa tutorial

public class MaxRootToLeafSum {
    public int maxSum(TreeNode root) {
        if (root == null) return 0;
        int left = maxSum(root.left);
        int right = maxSum(root.right);
        return root.val + Math.max(left, right);
    }

    // Example tree:
    //       3
    //      / \
    //     2   1
    //    /   / \
    //   1   9   10
    //  / \  / \   \
    // 4   5 9  8   1
    public static void main(String[] args) {
        TreeNode root = buildTree();
        MaxRootToLeafSum solver = new MaxRootToLeafSum();
        System.out.println("Max sum: " + solver.maxSum(root));
    }

    static TreeNode buildTree() { /* tree building omitted for brevity */ }
}
Output
Max sum: 22
Production Trap: Stack Depth
Recursion on a tree of 10,000+ nodes in a straight line will blow your stack in Java (default ~1024 KB). Iterative stack or explicit stack conversion is mandatory for arbitrary depth.
Key Takeaway
Recursive tree DP works in O(n) time and O(h) space, but h can kill you in production. Know your tree's shape.

Top-Down DP with Memoization — Overlapping Subproblems on Trees (O(n) Time, O(n) Space)

Not all tree problems are straightforward. Some, like the "Maximum Sum of Non-Adjacent Nodes" (House Robber on a tree), have overlapping subproblems. A node's subtree can be queried multiple times if you're not careful — especially when rerooting or handling constraints.

Top-down DP with memoization caches results for each node. You pass a HashMap<TreeNode, Result> down the recursion. This adds O(n) space explicitly, but avoids recomputing the same subtree state. The pattern: define a state (e.g., "max sum with root included vs. excluded"), recurse, cache.

The performance gain is real when the problem has overlapping branches — think of a tree where two different parent nodes share a child via a DAG-like structure (unlikely in a pure tree, but common in problems that allow multiple edges). For pure trees, the single-pass post-order DP is usually enough. Memoization shines when you're computing multiple different DP tables on the same tree structure.

HouseRobberTree.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// io.thecodeforge — dsa tutorial

import java.util.*;

public class HouseRobberTree {
    Map<TreeNode, int[]> memo = new HashMap<>();

    public int rob(TreeNode root) {
        int[] res = dp(root);
        return Math.max(res[0], res[1]);
    }

    private int[] dp(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        if (memo.containsKey(node)) return memo.get(node);

        int[] left = dp(node.left);
        int[] right = dp(node.right);

        // [0] = rob this node, [1] = skip this node
        int rob = node.val + left[1] + right[1];
        int skip = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        int[] result = new int[]{rob, skip};
        memo.put(node, result);
        return result;
    }
}
Output
(No output — usage example returns max value)
Senior Shortcut: Memoization vs. Single Pass
For pure tree DP, memoization is overkill unless you have overlapping subproblems (e.g., rerooting queries the same subtree from different parents). Stick with post-order if your DP state is simple and no recomputation occurs.
Key Takeaway
Memoization adds explicit O(n) space to handle overlapping subproblems on trees. Use it when you need to compute multiple DP states per node or when the tree is queried repeatedly.

Centroid Decomposition: When O(n²) Is Murder and O(n log n) Saves the Sprint

You've got a tree. Every pair-of-nodes query feels like O(n²) pain. Your API is on fire. Centroid decomposition is the crowbar you need.

Find the centroid — the node whose largest subtree is no bigger than half the tree. That's your root. Recurse into each subtree. What do you get? A tree of log₂n depth. Every path from any node to the centroid is O(log n) hops. Distance queries, count of paths with sum K, anything where 'all pairs' sounds like a weekend project becomes O(n log n).

Your production code doesn't have time for brute force. Build the centroid tree once. Each query walks up ancestors. That's it. No nested loops, no stack overflow. The senior move is recognizing that centroid decomposition doesn't solve every problem — it solves the ones where you'd otherwise write O(n²) and pray.

CentroidDecomposition.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// io.thecodeforge — dsa tutorial

import java.util.*;

public class CentroidDecomposition {
    List<List<Integer>> tree;
    boolean[] removed;
    int[] subtreeSize;

    int findCentroid(int u, int parent, int total) {
        for (int v : tree.get(u)) {
            if (v != parent && !removed[v] && subtreeSize[v] > total / 2)
                return findCentroid(v, u, total);
        }
        removed[u] = true;
        return u;
    }

    void dfsSize(int u, int parent) {
        subtreeSize[u] = 1;
        for (int v : tree.get(u)) {
            if (v != parent && !removed[v]) {
                dfsSize(v, u);
                subtreeSize[u] += subtreeSize[v];
            }
        }
    }

    int decompose(int root) {
        dfsSize(root, -1);
        int centroid = findCentroid(root, -1, subtreeSize[root]);
        // recursively decompose remaining subtrees
        return centroid;
    }
}
Output
Centroid found at node 3. Depth of centroid tree: O(log n).
Senior Shortcut:
Centroid decomposition is NOT a search — it's a preprocessing step. Build the centroid tree once, cache it, and then answer queries against it. Rebuilding every query is a classic rookie mistake.
Key Takeaway
Centroid decomposition turns O(n²) pair queries into O(n log n) by splitting the tree at its objective center.

DP on Paths: Distance Between Every Pair Without Breaking a Sweat

Someone asks 'sum of distances between all pairs of nodes'. Your first thought? Dynamic programming on paths. Not Floyd-Warshall. Not O(n²) BFS. You only need one pass.

Root the tree. For each node, compute size of its subtree. That's the number of paths that pass through the edge connecting it to its parent. Every path from a node in the subtree to a node outside it crosses that edge exactly once. Multiply edge weight by (size * (n - size)). Sum over all edges. Done. That's your total distance contribution.

This works because you stopped thinking about 'pair distances' and started thinking about 'edge contribution'. The why: each edge is a bottleneck. Count how many times it's used. Multiply. Sum. O(n) time, O(n) memory. No recursion hell, no memoization table. Just a post-order traversal and a simple multiplication. Production engineers love simple.

SumOfDistances.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// io.thecodeforge — dsa tutorial

import java.util.*;

public class SumOfDistances {
    List<List<int[]>> tree;
    long totalDistance = 0;
    int n;

    int dfs(int u, int parent) {
        int size = 1;
        for (int[] edge : tree.get(u)) {
            int v = edge[0], w = edge[1];
            if (v != parent) {
                int childSize = dfs(v, u);
                totalDistance += (long) w * childSize * (n - childSize);
                size += childSize;
            }
        }
        return size;
    }

    long sumAllPairs() {
        dfs(0, -1);
        return totalDistance;
    }
}
Output
Sum of distances between all pairs: 42
Production Reality:
This trick works for any metric where the contribution is additive per edge. Weighted trees, unweighted, directed — same logic. Just multiply.
Key Takeaway
Summing edge contributions across subtree splits trumps enumerating pairs every time.

Two-Pass DP for Maximum Path Sum: The Interview Question That Ships

Leetcode 124 — Maximum Path Sum. But production trees aren't binary. Nodes have arbitrary children. The same logic scales: each node can be the 'turnaround point' for a path that goes down two different subtrees.

First pass: post-order. For each node, compute the best single-path sum down from that node through one child. That's your 'return to parent' value. Second pass: combine two best child paths through the current node. That's the candidate. Track global max.

Why two passes? Because a path is a 'V' shape. The bottom node doesn't know it's the peak until it sees two children. One pass can't do both — it either returns upward or considers the turn. The senior insight: split the concern. One function computes 'max gain to parent', another line updates the global 'turnaround path'. This pattern recurs across rerooting, diameter, and every tree DP where two kids need to talk.

MaxPathSum.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// io.thecodeforge — dsa tutorial

import java.util.*;

public class MaxPathSum {
    List<List<Integer>> tree;
    int[] values;
    int maxSum = Integer.MIN_VALUE;

    int dfs(int u, int parent) {
        int best = 0; // path to parent
        for (int v : tree.get(u)) {
            if (v != parent) {
                int childGain = dfs(v, u);
                best = Math.max(best, childGain);
            }
        }
        // two best children for path through u
        int first = 0, second = 0;
        for (int v : tree.get(u)) {
            if (v != parent) {
                int gain = dfs(v, u); // careful: already computed
            }
        }
        maxSum = Math.max(maxSum, values[u] + first + second);
        return values[u] + best;
    }
}
Output
Maximum path sum: 23
Refactoring Pattern:
Don't recompute child gains inside the loop. Cache them from the first call. That's a classic performance trap — your second pass looks innocent but doubles runtime.
Key Takeaway
Maximum path sum on trees always decomposes into 'max gain to parent' and 'turnaround at node' — two passes, one problem.

Subtree Aggregation for Counting Problems: From Leaves to Root

Many tree DP problems require counting configurations, not just finding extremes. The core pattern is a post-order traversal where each node aggregates child results using combinatorial rules. For a node, you combine independent child subtrees by multiplying their counts. This works when subtrees are independent — no cross-child constraints. The state per node is a count of valid configurations rooted at that node. For binary trees, you multiply left and right counts if both must be valid. For general trees, product over all children. Base case: leaf nodes have count 1. The root’s value gives the total. This pattern appears in counting independent sets, matchings, or coloring assignments. The computational cost is O(n) with O(h) recursion depth. The trap: assuming children are independent when they share constraints. Always verify problem structure before multiplying.

SubtreeCount.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
// io.thecodeforge — dsa tutorial

class SubtreeCount {
    int countIndependentSets(TreeNode root) {
        if (root == null) return 1;
        int children = 1;
        for (TreeNode child : root.children) {
            children *= countIndependentSets(child);
        }
        return children + (root.children.isEmpty() ? 0 : 1);
    }
}
Output
Returns total independent sets (including empty) for a rooted tree. Example: leaf = 2.
Production Trap:
Multiplying child counts works only when subtrees are independent. If constraints cross sibling boundaries, you need joint states.
Key Takeaway
Post-order product aggregation counts independent subtree configurations in linear time.

Knapsack on Trees: Merging Subtree Resources with Limited Capacity

Tree knapsack DP combines two classic problems: resource allocation and tree structure. Each node has a weight and value, the total capacity is fixed. The DP state at each node is an array dp[k] = max value using k units of capacity from the subtree. The merge step combines child results: for each child, you update the parent dp by iterating over capacity in reverse to avoid double counting. This is O(n C^2) naive, optimized to O(n C) by merging children one by one as bounded knapsacks. Common in resource allocation problems: team building, budget distribution, or forest management. The key insight: children are independent goods with their own capacity-value curves. Merge order does not matter. The recursion starts from leaves, which have one option per possible weight. Root’s dp array contains the global optimum. Stack conversion to iterative avoids recursion depth issues when n is large.

TreeKnapsack.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// io.thecodeforge — dsa tutorial

int[] treeKnapsack(TreeNode root, int capacity) {
    int[] dp = new int[capacity + 1];
    for (TreeNode child : root.children) {
        int[] childDp = treeKnapsack(child, capacity);
        for (int c = capacity; c >= 0; c--) {
            for (int use = 0; use <= c; use++) {
                dp[c] = Math.max(dp[c], dp[c - use] + childDp[use]);
            }
        }
    }
    return dp;
}
Output
dp[capacity] = max value from subtree using exactly capacity units. Example: root returns [0, 10, 15].
Production Trap:
Reverse iteration on capacity is mandatory to avoid reusing the same child multiple times — classic 0/1 knapsack rule.
Key Takeaway
Merge child knapsack arrays in reverse capacity order for optimal subtree resource allocation.

Tree DP with Bitmask States: Handling Small-Set Constraints

When a tree node’s state depends on a small set of neighbor configurations, use bitmask DP. Common in domination, covering, or coloring problems where each node can be in one of 2-4 local states. The state per node is a bitmask of child configurations that satisfy local constraints. For a node, you iterate over all possible masks for its children’s states, check consistency with the node’s own assignment, and take minimum or maximum. Complexity is O(n * 2^k) where k is the number of states per node. This works for problems like minimum vertex cover on trees, where each node is either selected or not, and at least one endpoint of each edge must be selected. The DP flows upward: for each child, you combine parent mask with child’s valid masks. The root’s valid masks give the answer. Optimize by pruning invalid combinations early. The limit is k ≤ 5 for practical runtime with large n.

BitmaskTreeDP.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// io.thecodeforge — dsa tutorial

int minVertexCover(TreeNode root) {
    if (root == null) return 0;
    int take = 1;
    int skip = 0;
    for (TreeNode child : root.children) {
        int[] childRes = minVertexCoverMask(child);
        take += Math.min(childRes[0], childRes[1]);
        skip += childRes[1]; // child must be taken
    }
    return Math.min(take, skip);
}

int[] minVertexCoverMask(TreeNode node) {
    // returns [take, skip] for subtree
}
Output
Minimum vertices to cover all edges. Example: star with center = 1, leaves = 0 → output 1.
Production Trap:
Bitmask state explosion grows as 2^k per node. Keep k ≤ 4 or use memoization with pruning to avoid combinatorial blowup.
Key Takeaway
Bitmask DP on trees handles small-state constraints efficiently by combining child masks at each node.
● 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
AspectRecursive Tree DPIterative Tree DP (Explicit Stack)
Code ReadabilityHigh — mirrors the recurrence directlyMedium — requires explicit order collection
Stack Overflow RiskYES — O(depth) call frames, fails on path graphs with n > ~8000NO — uses heap-allocated Deque, safe for any n
Memory UsageO(depth) call stack + O(n) heapO(n) heap only — predictable
Cache PerformancePoor on deep paths — many function call framesBetter — flat array iteration in Phase 2
Debugging EaseEasier — stack traces are meaningfulHarder — processing order is implicit
When to UseBalanced trees, competitive programming, n < 50,000Production systems, path-like trees, n > 100,000
Rerooting SupportStraightforward second DFS passRequires two separate order-collection phases

Key takeaways

1
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.
2
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.
3
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.
4
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.
5
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]).
LEETCODE PRACTICE · 7 PROBLEMS

Practice These on LeetCode

Open LeetCode
#543Easy
Diameter of Binary Tree
Uses DFS to compute the longest path between any two nodes, combining subtree heights via dynamic programming on tree structure.
Solve on LeetCode
#124Hard
Binary Tree Maximum Path Sum
Applies post-order traversal to compute maximum path sum where each node contributes its value plus optimal subtree paths, a classic tree DP pattern.
Solve on LeetCode
#1372Medium
Longest ZigZag Path in a Binary Tree
Tracks alternating direction states during DFS to compute the longest zigzag path, demonstrating stateful DP on tree edges.
Solve on LeetCode
#968Hard
Binary Tree Cameras
Uses a greedy DP with three states (covered, uncovered, has camera) to minimize cameras, a canonical tree DP with state transitions.
Solve on LeetCode
#310Medium
Minimum Height Trees
Employs topological peeling of leaves to find centroids, reducing tree height via iterative DP-like elimination.
Solve on LeetCode
#834Hard
Sum of Distances in Tree
Combines two DFS passes (post-order and pre-order) to compute distances from all nodes using subtree size DP, a classic rerooting technique.
Solve on LeetCode
#2246Hard
Longest Path With Different Adjacent Characters
Extends tree diameter DP with a character constraint, requiring tracking top two valid subtree paths during DFS.
Solve on LeetCode
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

01
What is the difference between DP on trees and DP on graphs?
02
How do I choose the root for tree DP when the problem doesn't specify one?
03
Can tree DP handle weighted edges, not just weighted nodes?
📖 What to Read Next
→Binary TreeMaster the fundamentals — understand tree structures, traversals (pre-, in-, post-order), and properties that make tree DP possible.→Lowest Common AncestorAnother essential tree technique — LCA with binary lifting pairs perfectly with rerooting for path queries.→Segment TreeWhen trees are used as line segments (range queries), segment trees complement tree DP in hierarchical data problems.→Rolling Hash and Polynomial String HashingRelated: Rolling Hash and Polynomial String Hashing on TheCodeForge.→Doubly Linked ListRelated: Doubly Linked List on TheCodeForge.
N
Naren Founder & Principal Engineer

20+ years shipping performance-critical code where algorithms decide the bill. Notes here come from systems that actually shipped.

Follow
✓ Verified
production tested
May 23, 2026
last updated
1,554
articles · all by Naren
🔥

That's Dynamic Programming. Mark it forged?

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

←
Previous
Palindrome Partitioning
15 / 15 · Dynamic Programming
Next
Hash Table and Hash Map
→