Why does a post-order tree DP that combines every child at each node still run in O(n)?

## What a tree DP actually is A dynamic program is a set of subproblems plus an order in which they can be solved, where each subproblem depends only on subproblems already solved. On a rooted tree that structure is handed to you for free: the natural subproblem is "the answer for the subtree rooted at node `v`", and the dependencies point strictly downward — `dp[v]` is a function of `dp[c]` for the children `c` of `v`. Solving children before parents is therefore not a stylistic choice about traversal order; it is the only order in which the dependencies are satisfied. That is the whole reason a bottom-up (post-order) evaluation is the shape of every DP on a tree. ## The cost accounting, done correctly The common wrong answer is: "each of the `n` nodes loops over its children, and a node can have up to `n-1` children, so it is `O(n^2)`." The flaw is that the two factors are not independent. Charge the work to edges instead of to nodes: each execution of the loop body corresponds to exactly one parent-child pair, and every node except the root is somebody's child exactly once. A tree on `n` nodes has exactly `n-1` edges, so the loop body executes `n-1` times **in total across the whole traversal**, no matter how lopsided the branching is. A star with one node and `n-1` leaves costs the same total as a path. The general form of the bound: | factor | meaning | typical value | | --- | --- | --- | | `n` | nodes visited, once each | the tree size | | `S` | states stored per node | 2 for an include/exclude pair | | `c` | work per child, per state | `O(1)` for a sum or a max | Total time is `O(n * S * c)`. With a constant state count and a constant-time combine, that is `O(n)`. ## Where linearity actually breaks The bound assumes the combine is constant work **per child**. Three realistic ways to lose it: 1. **Pairwise combines.** If a node compares every pair of its children (rather than keeping a running best or a running sum), its cost is quadratic in its child count, and a star-shaped tree makes the total `O(n^2)`. 2. **Merging child tables.** When each node carries a table indexed by something like a budget or a count, merging two child tables costs the product of their sizes. Bounded by subtree sizes, the standard argument gives `O(n^2)` overall; bounded by a capacity `K`, it gives `O(n * K)`. Both are correct answers — but neither is `O(n)`, and claiming linearity there is a real error. 3. **Sorting children.** Sorting each node's children costs `O(k log k)` locally and `O(n log n)` overall. Usually unnecessary: a running top-one or top-two scan does the same job in one pass. ## Space is not free A recursive post-order DP holds one frame per ancestor of the node being processed, so its auxiliary space is `O(h)` where `h` is the height. On a balanced tree that is `O(log n)`, but nothing guarantees balance: a tree built from a chain of links is a path, and `h = n`. On large inputs this is a genuine crash, not a theoretical footnote, and the fix is to run the post-order with an explicit stack (or to convert to an iterative order by processing nodes in reverse of a discovery order). If you claim `O(1)` space because "we only keep a couple of numbers per node", you have forgotten that the stored states themselves are `O(n * S)` and the recursion is `O(h)`. ## Why no memo table is needed DP on a general dependency graph needs a table or a visited marker because the same subproblem is reachable from several predecessors. In a rooted tree every node has exactly one parent, so every subproblem is reached exactly once and the traversal *is* the memoization — the results are consumed by the single caller that needed them. One consequence worth stating out loud: if the input is an undirected link list with no designated root, you must still avoid walking back up, which is done by passing the parent down rather than by maintaining a global marker structure. ## What the interviewer is checking They want to hear the edge-counting argument, not the recital of a memorised `O(n)`. A candidate who can say "the loop body runs once per edge, there are `n-1` edges" can also tell you, unprompted, exactly which combine step would spoil it — and that second half is what separates a memorised bound from an understood one.