---
title: "DP on trees"
url: https://algopath.pro/patterns/dp-on-trees
language: en
summary: "Every node's answer is built out of the answers given by its own children. A single post-order pass computes all of them."
updated: 2026-08-24
---

# DP on trees

Every node's answer is built out of the answers given by its own children. A single post-order pass computes all of them.

## 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.

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

## When should you use DP on trees?

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

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

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

## 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.

```javascript
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;
}
```

## 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.

## JavaScript

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

## Python

```python
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)
```

## PHP

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