Tree DPDP on trees

01Why it exists

Reach for it when you see:Trees, subtrees, building a parent's answer from its children's answers, postorder traversal, take-or-skip decisions (adjacent nodes cannot both be taken), the diameter of a tree, the longest path through a given node, the answer with every node as the root (rerooting).

02The core idea

A tree has no cycles, so once you pick a node as the root, the subtrees hanging below each node are independent of one another — exactly the overlapping subproblems and optimal substructure that DP needs. Tree DP defines dp[u] for each node u as the answer when you look at u's subtree alone, computed purely from its children's dp values. The order of computation therefore has to be postorder: finish every child before handling the node itself. That is the same postorder traversal as in the Traversal lesson; only the return value changes, to whatever quantity the problem asks for.

Take the diameter of a tree, where two quantities have to be kept apart. down[u] is the longest chain going down from u, and it is what gets returned to the parent, because a parent can only attach a single straight chain. through[u] = left chain + right chain is the longest path that turns at u; it updates the global answer and is never returned. Correctness comes from one observation: every path in a tree has a unique highest node, and there the path is made of two downward chains, so computing through once at every node and taking the maximum cannot miss any path. The diameter need not pass through the root, which is why every node has to try to update the answer.

When each node carries a take-or-skip decision, store several states per node. The maximum weight independent set keeps take[u] and skip[u]: if u is taken, none of its children can be, so take[u] = w[u] + Σ skip[v]; if u is skipped, its children are free, so skip[u] = Σ max(take[v], skip[v]). Each edge is used exactly once, the moment its child finishes, so the total time is O(n); beyond the dp arrays, the recursion depth is the height of the tree, O(h), which degenerates to O(n) when the tree is a single chain. When you need the answer with every node as the root, use rerooting: one bottom-up pass computes the result for a fixed root, then a top-down pass carries the parent's answer down to each child in O(1). The whole thing is still O(n), rather than n runs of an O(n) algorithm.

Common pitfalls. Returning through — the turning path — to the parent gives you a "path" that actually forks. When node values can be negative (Binary Tree Maximum Path Sum), a subtree's chain has to be droppable, which means taking the maximum with 0. On a general tree stored as an adjacency list, the recursion has to remember the parent, or it will follow the undirected edge straight back. In Python, recursing over a chain-shaped tree of 100,000 nodes blows past the default limit of 1000, so lay out a parent-before-child order iteratively and process it in reverse. How this connects to other lessons: the height of a tree in Binary Tree Basics is the simplest tree DP of all; the one-dimensional "no two adjacent" of House Robber, moved onto a tree, is the maximum weight independent set; and camera coverage (Binary Tree Cameras) needs three states per node.

03The algorithm

1. 1Pick a root. On a general tree, use DFS or BFS to record each node's parent and to lay out an order in which a parent always comes before its children.
2. 2Decide what each node hands back to its parent (the longest downward chain, say, or the take/skip pair), and how that is computed from the children's values.
3. 3Process in postorder: a node is computed only once all its children are done. When the answer involves joining two subtrees at this node, update the global answer there as well, but still return only the part that can be attached upwards.
4. 4The answer sits at the root, or is the global maximum you recorded during the traversal.
5. 5If you need the answer with every node as the root, add one top-down rerooting pass that derives each child's answer from its parent's answer and subtree sizes in O(1).

04Interactive demo

A binary tree of 10 nodes, with its diameter found by postorder traversal. Every node computes two quantities: down, the longest chain going downwards, shown under the node and returned to its parent; and through, the left chain plus the right chain, used only to update the global answer. Blue is the node being processed, yellow are its children, green is the best diameter path so far, and grey marks the nodes not reached yet. The answer is updated first at G and D, and finally at B, where it becomes 6: H → G → D → B → E → I → J. By the time the root A is processed, the longest path through it is only 5 — this diameter never touches the root at all, which is exactly why every node has to try to update the answer.

05Code

Python covers the binary-tree diameter, the maximum path sum with negative values allowed, and the maximum weight independent set on a general tree using an iterative ordering (the party guest list from above). C++ covers the diameter of a general tree (joining the longest and second-longest chains) and a two-pass rerooting DP: the sum of distances from each node to all the others.

from collections import defaultdict


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


def diameter(root):
    """Diameter of a binary tree, in edges: return the longest downward chain, and use "left chain + right chain" to update the answer on the way"""
    best = 0

    def down(node):
        nonlocal best
        if node is None:
            return -1                          # an empty tree is -1, so a leaf's chain comes out as 0
        dl, dr = down(node.left) + 1, down(node.right) + 1
        best = max(best, dl + dr)              # the path that turns at node: only used to update the answer
        return max(dl, dr)                     # the parent can only be handed a single straight chain

    down(root)
    return best


def max_path_sum(root):
    """LeetCode 124: node values can be negative, so a chain that does not help is simply left out"""
    best = float("-inf")

    def gain(node):
        nonlocal best
        if node is None:
            return 0
        gl, gr = max(gain(node.left), 0), max(gain(node.right), 0)
        best = max(best, node.val + gl + gr)
        return node.val + max(gl, gr)

    gain(root)
    return best


def max_independent_set(n, edges, weight):
    """Maximum weight independent set on a general tree: two nodes joined by an edge cannot both be picked. An iterative order keeps recursion shallow"""
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    order, parent, seen, stack = [], [-1] * n, [False] * n, [0]
    seen[0] = True
    while stack:                               # first lay out an order where a parent always precedes its children
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if not seen[v]:
                seen[v], parent[v] = True, u
                stack.append(v)
    take, skip = weight[:], [0] * n            # take[u]: best for u's subtree when u is picked; skip[u]: when it is not
    for u in reversed(order):                  # go backwards, so every child is already done
        p = parent[u]
        if p != -1:
            take[p] += skip[u]                 # the parent was picked, so this child cannot be
            skip[p] += max(take[u], skip[u])   # the parent was skipped, so the child is free either way
    return max(take[0], skip[0])


if __name__ == "__main__":
    N = Node                                   # the same tree as the interactive demo
    tree = N("A", N("B", N("D", N("F"), N("G", None, N("H"))), N("E", None, N("I", None, N("J")))), N("C"))
    print(diameter(tree))                      # 6 (H-G-D-B-E-I-J, which never touches the root A)
    print(max_path_sum(N(-10, N(9), N(20, N(15), N(7)))))   # 42 (15 -> 20 -> 7)
    # Org chart: 0 is the CEO. A manager and a direct report are never both invited; maximise the total willingness score
    print(max_independent_set(7, [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)], [5, 3, 6, 4, 2, 3, 3]))   # 17

06Practice

• LeetCode 543Diameter of Binary TreeEasy
• LeetCode 337House Robber III (two states: take or skip)Medium
• LeetCode 124Binary Tree Maximum Path Sum (leave out negative chains)Hard
• LeetCode 968Binary Tree Cameras (three states per node)Hard
• LeetCode 2246Longest Path With Different Adjacent Characters (general-tree diameter: longest plus second longest)Hard
• LeetCode 834Sum of Distances in Tree (rerooting DP)Hard