DP on trees

How does DP on trees work?

Decide what one node returns to its parent. Often it is a pair, one value per choice.

Recurse into every child first. Nothing can be decided before they answer.

Combine the children's answers into this node's answer. That combination is the transition.

Return it upward. The parent knows nothing else about the subtree below.

Record a global best while unwinding, if the answer can sit anywhere. The root alone is not always enough.

One post-order pass touches each node once. That is the whole cost.

Sources: Wikipedia: Dynamic programming, Wikipedia: Tree traversal

1. leaf returns (3, 0)Robbing houses on a tree. Robbing the leaf gives 3, skipping gives 0.
2. node 2 returns (2, 3)Rob it and skip the child, or skip it and take the better.
3. node 3 returns (3, 1)Its own child is worth only 1.
4. root robbed = 3 + 3 + 1Robbing the root forces both children to be skipped.
5. answer = 7Seven beats the six that skipping the root would give.

function maxNonAdjacent(node) {
    if (!node) return [0, 0]; // [incl, excl]
    let inclSum = node.value;
    let exclSum = 0;
    for (const child of node.children) {
        const [inclC, exclC] = maxNonAdjacent(child);
        inclSum += exclC;
        exclSum += Math.max(inclC, exclC);
    }
    return [inclSum, exclSum];
}

interface TreeNode {
    value: number;
    children: TreeNode[];
}

function maxNonAdjacent(node: TreeNode | null): [number, number] {
    if (!node) return [0, 0]; // [incl, excl]
    let inclSum = node.value;
    let exclSum = 0;
    for (const child of node.children) {
        const [inclC, exclC] = maxNonAdjacent(child);
        inclSum += exclC;
        exclSum += Math.max(inclC, exclC);
    }
    return [inclSum, exclSum];
}

def max_non_adjacent(node):
    if node is None:
        return (0, 0)  # (incl, excl)
    incl_sum = node.value
    excl_sum = 0
    for child in node.children:
        incl_c, excl_c = max_non_adjacent(child)
        incl_sum += excl_c
        excl_sum += max(incl_c, excl_c)
    return (incl_sum, excl_sum)

function maxNonAdjacent(?Node $node): array {
    if ($node === null) return [0, 0]; // [incl, excl]
    $inclSum = $node->value;
    $exclSum = 0;
    foreach ($node->children as $child) {
        [$inclC, $exclC] = maxNonAdjacent($child);
        $inclSum += $exclC;
        $exclSum += max($inclC, $exclC);
    }
    return [$inclSum, $exclSum];
}

    // returns {incl, excl}: the best sum that takes this node, and the best that skips it
    public static int[] maxNonAdjacent(TreeNode node) {
        if (node == null) return new int[] { 0, 0 };
        int inclSum = node.value;
        int exclSum = 0;
        for (TreeNode child : node.children) {
            int[] best = maxNonAdjacent(child);
            inclSum += best[1];
            exclSum += Math.max(best[0], best[1]);
        }
        return new int[] { inclSum, exclSum };
    }

    public static class TreeNode {
        public int value;
        public List<TreeNode> children = new ArrayList<>();
    }

    // returns {incl, excl}: the best sum that takes this node, and the best that skips it
    public static int[] MaxNonAdjacent(TreeNode node) {
        if (node == null) return new int[] { 0, 0 };
        int inclSum = node.value;
        int exclSum = 0;
        foreach (var child in node.children) {
            int[] best = MaxNonAdjacent(child);
            inclSum += best[1];
            exclSum += Math.Max(best[0], best[1]);
        }
        return new int[] { inclSum, exclSum };
    }

    public class TreeNode {
        public int value;
        public List<TreeNode> children = new List<TreeNode>();
    }

A worked example of DP on trees

Largest sum along any path

Return the largest sum along any path in a binary tree.

A path may start and end anywhere, but it may not fork twice.

Each node returns the best straight path running down through it.

A negative branch is dropped. The best forking path is recorded globally while the calls unwind.

function maxPathSum(root) {
    let best = -Infinity;

    function down(node) {
        if (!node) return 0;

        // a negative branch is worse than taking nothing at all
        const left = Math.max(0, down(node.left));
        const right = Math.max(0, down(node.right));

        best = Math.max(best, node.val + left + right); // the fork stays local

        return node.val + Math.max(left, right); // the parent can only use one side
    }

    down(root);
    return best;
}

When should you use DP on trees?

Use DP on trees when the problem statement says “best choice over a hierarchy or org chart”, “cannot pick a node and its direct parent together” or “post-order: children settled before the parent”. A solution built on it usually runs in O(n).

• •best choice over a hierarchy or org chart
• •cannot pick a node and its direct parent together
• •post-order: children settled before the parent
• •each node combines states from its children

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is DP on trees confused with?

DP on trees is most often confused with Tree traversal, Dynamic programming (1-D), Recursion with memoization and Graph BFS / DFS.

• Tree traversal: That page is about the order of visiting. This one is about what gets carried back up.
• Dynamic programming (1-D): A line has one direction, so an index is enough. Here the tree structure sets the order.
• Recursion with memoization: A tree has no repeated subproblems, so no cache is needed. Each node is visited once.
• Graph BFS / DFS: A general graph can reach a node twice, so the recursion may not end. A tree cannot.

Common mistakes with DP on trees

• Returning the same value you record

  The value carried up is a straight path, but the best answer may fork. Keep the two apart.

• Computing before the children answer

  The transition needs both children first. Recurse first, then combine.

• Missing the empty-child case

  A node with one child still calls the other side. Return the neutral value there.

• Starting the best at zero

  Starting at zero hides a tree whose values are all negative. Start at minus infinity instead.

Which interview problems use DP on trees?

Interview problems solved with DP on trees include House robber III, Binary tree maximum path sum, Diameter of a binary tree, Longest univalue path, Distribute coins in a binary tree, Count good nodes and Binary tree tilt.

• House robber III: Two states per node: robbed or skipped.
• Binary tree maximum path sum: Return a straight path, record the fork.
• Diameter of a binary tree: Left depth plus right depth at each node.
• Longest univalue path: Extend only through children of equal value.
• Distribute coins in a binary tree: Push the surplus up to the parent.
• Count good nodes: Carry the maximum seen downward instead of up.
• Binary tree tilt: The difference between the two subtree sums.

What is the time and space complexity of DP on trees?

The target complexity of DP on trees is O(n).

n nodes give O(n) when each node does O(1) work. Several states per node multiply that.