Tree DP and the Rerooting Technique

                Mastery target: Level A recognition, progressing toward Level B implementation. You should be able to state each node's postorder return value, generalize the include/exclude recurrence to arbitrary trees, and explain why rerooting turns an $O(n^2)$ per-root recomputation into two $O(n)$ passes.
            

1. Problem and Motivation

Tree DP is dynamic programming where the recurrence follows the tree's parent-child structure instead of an array's linear index order. In array DP, $dp[i]$ is computed from $dp[i-1]$, $dp[i-2]$, and so on — a fixed, linear order of dependencies. In tree DP, a node's answer depends on its children's answers, and a node can have zero, one, two, or many children. The natural computation order is therefore a postorder traversal: visit every child subtree completely, combine what they return, and only then compute the current node's own answer.

This ordering is not optional. A parent's DP value is usually undefined until every child's DP value is known, exactly as $dp[i]$ in array DP is undefined until $dp[i-1]$ is known. The difference is that "the previous state" is no longer a single neighbor at index $i-1$ — it is a set of children, and the recurrence must specify how to combine an arbitrary number of child results into one parent result.

2. Prerequisites

This lesson builds directly on two earlier parts of the series and does not re-derive either one:

Tree traversal mechanics — postorder, preorder, and recursive tree walks are covered in Part 9: Trees, Tree Traversals. If postorder recursion (left, right, then process the node) is unfamiliar, read that section first.
The include/exclude DP idea — the array-based House Robber recurrence, $dp[i] = \max(dp[i-1],\, dp[i-2] + nums[i])$, is fully covered in Part 15: Core DP Patterns, section 4, House Robber. This lesson generalizes that same include/exclude idea from a linear array to a tree; it does not re-derive it from scratch.

Also assumed: recursion, basic tree/graph adjacency representations, and arithmetic with array indices.

3. A Concrete Example

Worked Example

Binary-Tree House Robber, hand-traced

Tree (LeetCode 337, Example 1): root value 3, whose left child is 2 and right child is another 3. Node 2 has only a right child valued 3. The root's right child (3) has only a right child valued 1.

Postorder visits the leaves first. Each node returns a pair (with, without): the best loot from its subtree if the node itself IS robbed, and the best loot if it is NOT.

Node	Children processed	with = val + left.without + right.without	without = max(left pair) + max(right pair)
leaf 3 (under node 2)	none	3 + 0 + 0 = 3	0 + 0 = 0
leaf 1 (under root's right 3)	none	1 + 0 + 0 = 1	0 + 0 = 0
node 2	no left child; right = leaf 3 → (3, 0)	2 + 0 + 0 = 2	max(0,0) + max(3,0) = 0 + 3 = 3
node 3 (root's right child)	no left child; right = leaf 1 → (1, 0)	3 + 0 + 0 = 3	max(0,0) + max(1,0) = 0 + 1 = 1
root (val 3)	left = node 2 → (2, 3); right = node 3 → (3, 1)	3 + 3 + 1 = 7	max(2,3) + max(3,1) = 3 + 3 = 6

The root's pair is (7, 6), so the answer is max(7, 6) = 7 — rob the root, the leaf under node 2, and the leaf under the root's right child. This is exactly the published answer for this input.

Notice the shape of the computation: every pair bubbles up from leaves to root, and the parent's pair is a pure function of its children's pairs. That is the entire postorder tree-DP pattern.

4. Postorder State Aggregation and Include/Exclude States

                Core insight: Each node returns a pair of values — the best answer if this node IS included in the selection, and the best answer if it is NOT — and the parent combines its children's pairs to compute its own pair. This exactly generalizes the array-based House Robber recurrence ($dp[i] = \max(dp[i-1],\, dp[i-2]+nums[i])$) to a tree: "the previous element" becomes "each child," and "skip one, take two back" becomes "a robbed node forces its children to be unrobbed."
            

For a node $u$ with children $c_1, \ldots, c_k$:

$$with(u) = val(u) + \sum_{i} without(c_i)$$

$$without(u) = \sum_{i} \max(with(c_i),\, without(c_i))$$

A missing child contributes the pair $(0, 0)$, which keeps the formula uniform for nodes with zero, one, or two children. The final answer is $\max(with(root), without(root))$.

The implementation below solves Binary-Tree House Robber (LeetCode 337) for the general case of a binary tree — the same pair-return technique extends unchanged to a node with any number of children by summing $without(c_i)$ and $\max(with(c_i), without(c_i))$ over all children instead of just two.

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def rob_tree(root):
    """
    LeetCode 337: House Robber III.
    Each node returns (with_node, without_node):
      with_node    = best loot from this subtree if this node IS robbed
      without_node = best loot from this subtree if this node is NOT robbed
    A robbed node cannot have robbed children, so with_node adds the
    'without' value of both children. without_node is free to take the
    better of each child's two states.
    Time: O(n) - one postorder visit per node. Space: O(h) recursion stack.
    """
    def dfs(node):
        if node is None:
            return (0, 0)  # (with, without) for an empty subtree
        left_with, left_without = dfs(node.left)
        right_with, right_without = dfs(node.right)
        with_node = node.val + left_without + right_without
        without_node = max(left_with, left_without) + max(right_with, right_without)
        return (with_node, without_node)

    best_with, best_without = dfs(root)
    return max(best_with, best_without)


# Tree: [3,2,3,null,3,null,1] -> expected 7
root = TreeNode(3,
                TreeNode(2, None, TreeNode(3)),
                TreeNode(3, None, TreeNode(1)))
print("Max loot:", rob_tree(root))  # Max loot: 7

#include <iostream>
#include <algorithm>
#include <utility>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(v), left(l), right(r) {}
};

// Returns {with_node, without_node} for the subtree rooted at node.
std::pair<int, int> dfs(TreeNode* node) {
    if (node == nullptr) {
        return {0, 0};
    }
    auto [leftWith, leftWithout] = dfs(node->left);
    auto [rightWith, rightWithout] = dfs(node->right);
    int withNode = node->val + leftWithout + rightWithout;
    int withoutNode = std::max(leftWith, leftWithout) + std::max(rightWith, rightWithout);
    return {withNode, withoutNode};
}

int robTree(TreeNode* root) {
    auto [bestWith, bestWithout] = dfs(root);
    return std::max(bestWith, bestWithout);
}

int main() {
    TreeNode* root = new TreeNode(3,
                        new TreeNode(2, nullptr, new TreeNode(3)),
                        new TreeNode(3, nullptr, new TreeNode(1)));
    std::cout << "Max loot: " << robTree(root) << '\n';  // Max loot: 7
}

public class BinaryTreeHouseRobber {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // result[0] = withNode, result[1] = withoutNode
    static int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int withNode = node.val + left[1] + right[1];
        int withoutNode = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{withNode, withoutNode};
    }

    static int robTree(TreeNode root) {
        int[] result = dfs(root);
        return Math.max(result[0], result[1]);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3,
                            new TreeNode(2, null, new TreeNode(3, null, null)),
                            new TreeNode(3, null, new TreeNode(1, null, null)));
        System.out.println("Max loot: " + robTree(root)); // Max loot: 7
    }
}

5. Tree Knapsack (Choosing k Nodes)

                Core insight: Combine tree DP with a knapsack-style budget. $dp[node][j]$ = best value achievable in node's subtree using at most $j$ "budget units" (node count, weight, or any additive resource). Each child's dp array is merged into the parent's using a knapsack-style merge, one child at a time.
            

Consider: select a subset of nodes, of size at most $k$, to maximize total value, where a node may be selected only if its parent is also selected (the root has no such restriction). Let $dp[u]$ be an array indexed by budget $j$ from $0$ to $size(u)$, the size of $u$'s subtree. Build it by merging children one at a time: start with a one-element array $[0]$ (nothing selected yet), and for each child $c$, combine the current partial array with $dp[c]$ using $new[j+t] = \max(new[j+t],\, partial[j] + dp[c][t])$. After all children are merged, prefix-max the result so it means "at most" $j$, then set $dp[u][j] = val(u) + merged[j-1]$ for $j \ge 1$ (selecting $u$ costs one unit and unlocks its children), and $dp[u][0] = 0$.

Why the merge is O(n) total, not O(n × budget) per node

At first glance, merging a child of subtree size $s_c$ into a running array of size $s_u$ costs $O(s_u \cdot s_c)$, and summing that over every node looks like it could be quadratic in the budget. The classic result is better: if every merge is capped at the size of the two subtrees actually being combined (as above, not at some global budget $k$), the total merge work across the whole tree is $O(n^2)$ in the worst case — not $O(n \times k)$ per node repeated $n$ times. This falls out of the small-to-large (also called "size doubling") argument: each pair of nodes $(x, y)$ can only be "merged together" once, at the moment their two subtrees first combine into a common ancestor's subtree, and that single merge costs at most $O(size(x) \cdot size(y))$. Summing $size(x)\cdot size(y)$ over all such first-merge pairs across the tree telescopes to $O(n^2)$ total in the worst case (a "broom" or balanced binary tree), which is the same bound naive analysis gives — the value of the small-to-large argument is that it also proves tighter bounds (e.g. $O(n \sqrt n)$ or $O(n\log n)$) hold for many other subtree-merge DPs where the accounting is less trivial. The practical takeaway: always cap each merge at the true combined subtree size, never at the global budget $k$, or the naive-looking bound becomes a real one.

def tree_knapsack(n, edges, values, root, k):
    """
    Select at most k nodes to maximize total value, where a node can only
    be selected if its parent is also selected. dp[node][j] = best value
    achievable in node's subtree using at most j selected nodes drawn
    from that subtree.

    Each child's dp array is merged in one at a time, capped at the
    *combined* subtree size seen so far (small-to-large accounting),
    which is why total merge work is O(n^2) worst case across the whole
    tree rather than O(n * k) repeated at every node.
    Time: O(n^2) worst case, Space: O(n).
    """
    children = [[] for _ in range(n)]
    for u, v in edges:
        children[u].append(v)

    size = [0] * n
    dp = [None] * n

    def dfs(u):
        size[u] = 1
        merged = [0]  # merged[t] = best value using at most t child-side nodes
        for v in children[u]:
            dfs(v)
            new_size = size[u] + size[v]
            new_merged = [0] * (new_size + 1)
            for j in range(len(merged)):
                base = merged[j]
                for t in range(len(dp[v])):
                    if j + t <= new_size and base + dp[v][t] > new_merged[j + t]:
                        new_merged[j + t] = base + dp[v][t]
            merged = new_merged
            size[u] += size[v]
        for t in range(1, len(merged)):
            merged[t] = max(merged[t], merged[t - 1])  # merged[t] now means "at most t"
        dp_u = [0] * (size[u] + 1)
        for j in range(1, size[u] + 1):
            dp_u[j] = values[u] + merged[j - 1]
        for j in range(1, len(dp_u)):
            dp_u[j] = max(dp_u[j], dp_u[j - 1])
        dp[u] = dp_u

    dfs(root)
    return dp[root][min(k, size[root])]


# Tree: 0->1, 0->2, 1->3, 1->4
edges = [(0, 1), (0, 2), (1, 3), (1, 4)]
values = [3, 5, 1, 8, 2]
for k in range(6):
    print(f"k={k}: best value = {tree_knapsack(5, edges, values, 0, k)}")
# k=0: 0, k=1: 3, k=2: 8, k=3: 16, k=4: 18, k=5: 19

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<std::vector<int>> dp;
std::vector<int> subtreeSize;
std::vector<std::vector<int>> children;
std::vector<int> values;

void dfs(int u) {
    subtreeSize[u] = 1;
    std::vector<int> merged = {0};
    for (int v : children[u]) {
        dfs(v);
        int newSize = subtreeSize[u] + subtreeSize[v];
        std::vector<int> newMerged(newSize + 1, 0);
        for (int j = 0; j < (int)merged.size(); ++j) {
            for (int t = 0; t < (int)dp[v].size(); ++t) {
                if (j + t <= newSize) {
                    newMerged[j + t] = std::max(newMerged[j + t], merged[j] + dp[v][t]);
                }
            }
        }
        merged = newMerged;
        subtreeSize[u] += subtreeSize[v];
    }
    for (int t = 1; t < (int)merged.size(); ++t) {
        merged[t] = std::max(merged[t], merged[t - 1]);
    }
    std::vector<int> dpU(subtreeSize[u] + 1, 0);
    for (int j = 1; j <= subtreeSize[u]; ++j) {
        dpU[j] = values[u] + merged[j - 1];
    }
    for (int j = 1; j < (int)dpU.size(); ++j) {
        dpU[j] = std::max(dpU[j], dpU[j - 1]);
    }
    dp[u] = dpU;
}

int treeKnapsack(int n, const std::vector<std::pair<int,int>>& edges,
                  const std::vector<int>& nodeValues, int root, int k) {
    children.assign(n, {});
    for (auto& e : edges) children[e.first].push_back(e.second);
    values = nodeValues;
    dp.assign(n, {});
    subtreeSize.assign(n, 0);
    dfs(root);
    int budget = std::min(k, subtreeSize[root]);
    return dp[root][budget];
}

int main() {
    std::vector<std::pair<int,int>> edges = {{0,1},{0,2},{1,3},{1,4}};
    std::vector<int> values5 = {3,5,1,8,2};
    for (int k = 0; k <= 5; ++k) {
        std::cout << "k=" << k << ": best value = "
                   << treeKnapsack(5, edges, values5, 0, k) << '\n';
    }
    // k=0: 0, k=1: 3, k=2: 8, k=3: 16, k=4: 18, k=5: 19
}

import java.util.*;

public class TreeKnapsack {
    static List<List<Integer>> children;
    static int[] values;
    static int[] size;
    static int[][] dp;

    static void dfs(int u) {
        size[u] = 1;
        int[] merged = {0};
        for (int v : children.get(u)) {
            dfs(v);
            int newSize = size[u] + size[v];
            int[] newMerged = new int[newSize + 1];
            for (int j = 0; j < merged.length; j++) {
                for (int t = 0; t < dp[v].length; t++) {
                    if (j + t <= newSize) {
                        newMerged[j + t] = Math.max(newMerged[j + t], merged[j] + dp[v][t]);
                    }
                }
            }
            merged = newMerged;
            size[u] += size[v];
        }
        for (int t = 1; t < merged.length; t++) {
            merged[t] = Math.max(merged[t], merged[t - 1]);
        }
        int[] dpU = new int[size[u] + 1];
        for (int j = 1; j <= size[u]; j++) {
            dpU[j] = values[u] + merged[j - 1];
        }
        for (int j = 1; j < dpU.length; j++) {
            dpU[j] = Math.max(dpU[j], dpU[j - 1]);
        }
        dp[u] = dpU;
    }

    static int treeKnapsack(int n, int[][] edges, int[] nodeValues, int root, int k) {
        children = new ArrayList<>();
        for (int i = 0; i < n; i++) children.add(new ArrayList<>());
        for (int[] e : edges) children.get(e[0]).add(e[1]);
        values = nodeValues;
        dp = new int[n][];
        size = new int[n];
        dfs(root);
        int budget = Math.min(k, size[root]);
        return dp[root][budget];
    }

    public static void main(String[] args) {
        int[][] edges = {{0,1},{0,2},{1,3},{1,4}};
        int[] values = {3,5,1,8,2};
        for (int k = 0; k <= 5; k++) {
            System.out.println("k=" + k + ": best value = " + treeKnapsack(5, edges, values, 0, k));
        }
        // k=0: 0, k=1: 3, k=2: 8, k=3: 16, k=4: 18, k=5: 19
    }
}

6. BST-Shape DP

Counting structurally distinct binary search trees is a shorter but instructive tree-DP shape: it builds trees rather than consuming a given one. Let $dp[n]$ be the number of structurally distinct BSTs holding $n$ distinct keys. Choosing which key becomes the root at position $i$ (for $i = 1 \ldots n$) splits the remaining keys into a left subtree of size $i-1$ and a right subtree of size $n-i$; the two subtrees vary independently, so their shape counts multiply:

$$dp[n] = \sum_{i=1}^{n} dp[i-1] \cdot dp[n-i], \qquad dp[0] = 1$$

This is precisely the Catalan number recurrence — $dp[n]$ is the $n$-th Catalan number, $C_n$. This lesson only needs the recurrence and the connection, not a derivation of the closed form $C_n = \frac{1}{n+1}\binom{2n}{n}$.

def count_distinct_bsts(n):
    """
    dp[n] = number of structurally distinct BSTs with n nodes labeled 1..n.
    dp[n] = sum over i=1..n of dp[i-1] * dp[n-i] (Catalan number recurrence).
    Time: O(n^2), Space: O(n).
    """
    dp = [0] * (n + 1)
    dp[0] = 1  # one shape: the empty tree
    for nodes in range(1, n + 1):
        total = 0
        for i in range(1, nodes + 1):
            total += dp[i - 1] * dp[nodes - i]
        dp[nodes] = total
    return dp[n]


for n in range(6):
    print(f"n={n}: {count_distinct_bsts(n)} distinct BST shapes (Catalan number C_{n})")
# n=0: 1, n=1: 1, n=2: 2, n=3: 5, n=4: 14, n=5: 42

#include <iostream>
#include <vector>

long long countDistinctBSTs(int n) {
    std::vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    for (int nodes = 1; nodes <= n; ++nodes) {
        long long total = 0;
        for (int i = 1; i <= nodes; ++i) {
            total += dp[i - 1] * dp[nodes - i];
        }
        dp[nodes] = total;
    }
    return dp[n];
}

int main() {
    for (int n = 0; n <= 5; ++n) {
        std::cout << "n=" << n << ": " << countDistinctBSTs(n) << " distinct BST shapes\n";
    }
    // n=0: 1, n=1: 1, n=2: 2, n=3: 5, n=4: 14, n=5: 42
}

public class BSTShapeCount {
    static long countDistinctBSTs(int n) {
        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int nodes = 1; nodes <= n; nodes++) {
            long total = 0;
            for (int i = 1; i <= nodes; i++) {
                total += dp[i - 1] * dp[nodes - i];
            }
            dp[nodes] = total;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        for (int n = 0; n <= 5; n++) {
            System.out.println("n=" + n + ": " + countDistinctBSTs(n) + " distinct BST shapes");
        }
        // n=0: 1, n=1: 1, n=2: 2, n=3: 5, n=4: 14, n=5: 42
    }
}

7. Rerooting Technique

                Core insight: Some problems need the tree-DP answer computed with EVERY node as the root — for example, "for each node, what is the sum of distances to every other node if this node were the root." Naively that costs $O(n^2)$: one full traversal per candidate root. Rerooting instead does ONE postorder pass rooted at an arbitrary fixed node, then a SECOND preorder pass that re-derives each node's answer as root by combining its postorder subtree answer with information flowing down from its parent.
            

Concrete problem: for each node $u$ in an unrooted tree of $n$ nodes, compute the sum of distances from $u$ to every other node. Root the tree arbitrarily at node 0.

Pass 1 (postorder): for each node $u$, compute $count[u]$ = size of $u$'s subtree, and $down[u]$ = sum of distances from $u$ to every node inside its own subtree, using $down[u] = \sum_{c} \big(down[c] + count[c]\big)$ over children $c$ (each node in $c$'s subtree is one edge farther from $u$ than it is from $c$, hence the $+count[c]$ term). $ans[0] = down[0]$, since node 0's subtree is the whole tree.

Pass 2 (preorder): re-derive $ans[c]$ for each child $c$ of a node $u$ whose answer is already known. Moving the root from $u$ to $c$ changes the distance to every other node by exactly $\pm 1$: the $count[c]$ nodes inside $c$'s subtree all get one edge closer (they were measured through $u$, one hop farther than necessary), and the remaining $n - count[c]$ nodes outside $c$'s subtree all get one edge farther (reaching them from $c$ now requires the extra hop back through $u$). So:

$$ans[c] = ans[u] - count[c] + (n - count[c])$$

This is the step that is easy to get subtly wrong: it is not $ans[u] - down[c]$ or a recomputation from scratch — it reuses $ans[u]$ (the parent's already-finished answer over the entire tree) and adjusts it by exactly the $count[c]$ nodes that changed side, never touching $down[c]$ again. A worked check on a 6-node tree (root 0 with children 1 and 2; node 2 has children 3, 4, 5) gives $ans = [8, 12, 6, 10, 10, 10]$, matching a brute-force BFS-from-every-node computation exactly.

def sum_of_distances(n, edges):
    """
    For each node, compute the sum of distances to every other node in
    an unrooted tree, using rerooting so all n answers cost O(n) total
    instead of O(n^2) for n separate BFS/DFS runs.

    Pass 1 (postorder, tree rooted arbitrarily at node 0):
      count[u] = size of u's subtree
      down[u]  = sum of distances from u to every node in u's own subtree

    Pass 2 (preorder): re-derive the answer for u AS ROOT from its
    parent's already-known answer. Moving the root from parent p to
    child c changes every node's distance to the new root by +1 if the
    node is outside c's subtree (n - count[c] such nodes), and by -1 if
    it is inside c's subtree (count[c] such nodes, since they were
    measured one edge farther via p). So:
        ans[c] = ans[p] - count[c] + (n - count[c])
    Time: O(n), Space: O(n).
    """
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    count = [1] * n
    down = [0] * n

    def post(u, parent):
        for v in adj[u]:
            if v == parent:
                continue
            post(v, u)
            count[u] += count[v]
            down[u] += down[v] + count[v]

    post(0, -1)

    ans = [0] * n
    ans[0] = down[0]

    def pre(u, parent):
        for v in adj[u]:
            if v == parent:
                continue
            ans[v] = ans[u] - count[v] + (n - count[v])
            pre(v, u)

    pre(0, -1)
    return ans


# Tree: 0-1, 0-2, 2-3, 2-4, 2-5
edges = [(0, 1), (0, 2), (2, 3), (2, 4), (2, 5)]
print(sum_of_distances(6, edges))  # [8, 12, 6, 10, 10, 10]

#include <iostream>
#include <vector>

int n;
std::vector<std::vector<int>> adj;
std::vector<int> subtreeCount, down, ans;

void post(int u, int parent) {
    subtreeCount[u] = 1;
    for (int v : adj[u]) {
        if (v == parent) continue;
        post(v, u);
        subtreeCount[u] += subtreeCount[v];
        down[u] += down[v] + subtreeCount[v];
    }
}

void pre(int u, int parent) {
    for (int v : adj[u]) {
        if (v == parent) continue;
        ans[v] = ans[u] - subtreeCount[v] + (n - subtreeCount[v]);
        pre(v, u);
    }
}

std::vector<int> sumOfDistances(int nodes, const std::vector<std::pair<int,int>>& edges) {
    n = nodes;
    adj.assign(n, {});
    subtreeCount.assign(n, 0);
    down.assign(n, 0);
    ans.assign(n, 0);
    for (auto& e : edges) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
    }
    post(0, -1);
    ans[0] = down[0];
    pre(0, -1);
    return ans;
}

int main() {
    std::vector<std::pair<int,int>> edges = {{0,1},{0,2},{2,3},{2,4},{2,5}};
    auto result = sumOfDistances(6, edges);
    for (int i = 0; i < (int)result.size(); ++i) {
        std::cout << result[i] << (i + 1 < (int)result.size() ? ", " : "\n");
    }
    // 8, 12, 6, 10, 10, 10
}

import java.util.*;

public class SumOfDistances {
    static int n;
    static List<List<Integer>> adj;
    static int[] count, down, ans;

    static void post(int u, int parent) {
        count[u] = 1;
        for (int v : adj.get(u)) {
            if (v == parent) continue;
            post(v, u);
            count[u] += count[v];
            down[u] += down[v] + count[v];
        }
    }

    static void pre(int u, int parent) {
        for (int v : adj.get(u)) {
            if (v == parent) continue;
            ans[v] = ans[u] - count[v] + (n - count[v]);
            pre(v, u);
        }
    }

    static int[] sumOfDistances(int nodes, int[][] edges) {
        n = nodes;
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        count = new int[n];
        down = new int[n];
        ans = new int[n];
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        post(0, -1);
        ans[0] = down[0];
        pre(0, -1);
        return ans;
    }

    public static void main(String[] args) {
        int[][] edges = {{0,1},{0,2},{2,3},{2,4},{2,5}};
        int[] result = sumOfDistances(6, edges);
        System.out.println(Arrays.toString(result));
        // [8, 12, 6, 10, 10, 10]
    }
}

8. Complexity Analysis

Binary-Tree House Robber: $O(n)$ time, $O(h)$ recursion-stack space — a single postorder visit per node, each doing $O(1)$ work.

BST-Shape DP: $O(n)$ states, each costing $O(n)$ to compute via the sum over root positions, giving $O(n^2)$ total for a bottom-up table (or a memoized recursion visiting the same $O(n)$ distinct subproblems).

Tree Knapsack: $O(n^2)$ worst case for the merge, via the small-to-large subtree-size argument described above — not the naive-looking $O(n \times budget)$ per node, which would overcount work already bounded by actual subtree sizes. Many tree-knapsack variants tighten this further to $O(n \log n)$ with more careful accounting, but $O(n^2)$ is the safe, provable bound for the merge shown here.

Rerooting: $O(n)$ total — one postorder pass plus one preorder pass, each visiting every node once and doing $O(1)$ (or $O(\deg(u))$) work per node, versus $O(n^2)$ for recomputing the full DP from scratch at every candidate root.

9. Applications and Alternatives

Where tree DP and rerooting show up in practice

Network diameter and eccentricity: rerooting computes, for every router or node in a network topology, its eccentricity (maximum distance to any other node) in $O(n)$ instead of running BFS from every node.
Organizational hierarchy optimization: selecting a budget-constrained subset of roles or teams to fund, where funding a role requires its manager's role to also be funded, is a direct instance of the tree knapsack "parent must be selected" constraint.
Phylogenetic tree analysis: computing the sum (or centroid) of evolutionary distances from every species node to all others reuses the same rerooting recombination as the sum-of-distances example, since phylogenetic trees are also unrooted by nature.

When the tree is small or the answer is only needed for one fixed root, a single postorder DP pass is simpler and sufficient — reach for rerooting specifically when the same tree-DP quantity is required for every node as root, since a full re-run per root turns an $O(n)$ algorithm into an $O(n^2)$ one.

10. Exercises and Mastery

Easy

Trace the Binary-Tree House Robber pair algorithm on a new 5-node tree of your own construction (a root with two children, each with one grandchild), and verify the pair returned by the root by hand.
State, in your own words, why a missing child contributes the pair $(0, 0)$ rather than being skipped in the summation.

Medium

Run the BST-Shape DP for $n=5$ and verify the result equals the known Catalan number $C_5 = 42$. Show the five terms of the sum $dp[5] = \sum_{i=1}^{5} dp[i-1]\cdot dp[5-i]$ that add up to 42.
Modify the tree knapsack example so a node's "cost" is its own value (not a flat 1 per node), and describe which part of the merge recurrence must change.

Hard

Use rerooting to find a tree's diameter: for each node, compute the maximum distance to any other node (rather than the sum), then take the overall maximum across all nodes and identify the two endpoint nodes that realize it. Verify your rerooting recombination step for maximum distance differs from the sum-of-distances recombination — it is not a simple $\pm 1$ shift, since the maximum, unlike the sum, is not decomposable by "how many nodes changed side."

Mastery challenge: A company's org chart is a tree where funding a team also requires funding every team above it up to the root. Given a fixed total headcount budget, choose which teams to fund to maximize total projected impact. Define the DP state, specify the merge order and complexity, and explain how rerooting would (or would not) help if the constraint were relaxed so funding could start from any node instead of only the root.

Review rhythm: tomorrow, re-derive the include/exclude pair recurrence from memory and re-trace the worked example; next week, implement the tree knapsack merge and the rerooting recombination step in a language you have not used here; several weeks later, find a new problem — network eccentricity, subtree counting, or a fresh LeetCode tree problem — and identify which of these four patterns it matches before looking up a solution.

11. Summary Cheat Sheet

Tree DP follows the tree's parent-child structure via postorder traversal: children's answers are computed before the parent's.
Include/exclude on a tree generalizes the array House Robber recurrence: each node returns a (with, without) pair, combined from its children's pairs.
Tree knapsack merges children's budgeted dp arrays one at a time; capping each merge at the true combined subtree size (small-to-large) keeps total work bounded, unlike naively multiplying by a global budget.
BST-Shape DP counts structurally distinct trees by summing over root-position choices; the recurrence is the Catalan number recurrence.
Rerooting computes a tree-DP answer for every node as root using one postorder pass (subtree answers) plus one preorder pass (parent-to-child recombination), turning $O(n^2)$ into $O(n)$.
The rerooting recombination step reuses the parent's finished answer and adjusts only for the nodes that changed side of the moved edge — it never recomputes from scratch.

Cookie Consent

Tree Dynamic Programming and the Rerooting Technique

Table of Contents

1. Problem and Motivation

2. Prerequisites

3. A Concrete Example

Binary-Tree House Robber, hand-traced

4. Postorder State Aggregation and Include/Exclude States

5. Tree Knapsack (Choosing k Nodes)

Why the merge is O(n) total, not O(n × budget) per node

6. BST-Shape DP

7. Rerooting Technique

8. Complexity Analysis

9. Applications and Alternatives

Where tree DP and rerooting show up in practice

10. Exercises and Mastery

Easy

Medium

Hard

11. Summary Cheat Sheet

Cookie Consent

Tree Dynamic Programming and the Rerooting Technique

Table of Contents

1. Problem and Motivation

2. Prerequisites

3. A Concrete Example

Binary-Tree House Robber, hand-traced

4. Postorder State Aggregation and Include/Exclude States

5. Tree Knapsack (Choosing k Nodes)

Why the merge is O(n) total, not O(n × budget) per node

6. BST-Shape DP

7. Rerooting Technique

8. Complexity Analysis

9. Applications and Alternatives

Where tree DP and rerooting show up in practice

10. Exercises and Mastery

Easy

Medium

Hard

11. Summary Cheat Sheet

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Part 9: Trees, Tree Traversals

Part 15: Core DP Patterns