Dynamic Programming21 sections · 916 units
Open in Course

Why Post-Order?

Children before parents

Post-order DFS visits children before the parent. When you return from recursing on all children, their dp values are ready. You combine them to compute dp[parent]dp[\text{parent}].

function dfs(v, parent)
    for each child in neighbors[v]
        if child  parent then
            dfs(child, v)
    dp[v] := combine children's dp values

The parent check prevents going back up the edge you came from. Without it, you'd treat your parent as a child and recurse forever. Post-order keeps children are processed before their parent. You need child answers to compute the parent answer.