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.

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];
}

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?

These phrases in a problem statement point here:

• •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

What is DP on trees confused with?

• 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

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

Which interview problems use DP on trees?

• 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?

O(n)

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