DP on trees

O(n)

Walk the tree bottom-up (post-order): each node returns two numbers built from its children, one assuming the node is taken and one assuming it's skipped. The parent combines whichever fits its own rule.

Signals

best choice over a hierarchy or org chartcannot pick a node and its direct parent togetherpost-order: children settled before the parenteach node combines states from its children

Template

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

Looks similar, isn't

Tree traversal: A plain traversal just visits every node once with no memory of what a child decided. Tree DP has each node return one or more states, like included/excluded, built from what its children reported, so a parent can combine them under a rule such as never picking both a node and its child.

n up to 1e5 nodes, one post-order visit per node returning a couple numbers -> O(n): each node combines its children's states exactly once.

Learn this pattern