skip to content

In a tree DP that forbids picking a node and its parent together, why keep two values per node?

level: middleimportance: must knowfreq 55%

answer

  1. one number per node loses information
  2. a parent's choice constrains its children
  3. what must the parent know about each child?
  4. answers conditioned on the node's own decision
  5. taken versus skipped, combined at the parent

basics

~20 s

Keep two numbers per node: the best subtree total with that node picked, and with it skipped. A parent that picks itself needs its children's skipped totals, so collapsing to one best-per-node throws away exactly the value the parent needs.

solid answer

~50 s

Take an org chart where each employee has a seniority score and no manager may serve on a committee together with a direct report. If each node returned only its subtree's best total, the parent could not use it — the parent's own choice constrains what the child is allowed to do, and one number cannot answer "best if you are on" and "best if you are off" at once. So store both: `with[v] = score[v] + sum over children of without[c]`, and `without[v] = sum over children of max(with[c], without[c])`. The subtle half is that `without[v]` takes a **max** per child, not a forced inclusion: skipping `v` merely lifts the constraint, it does not oblige the children to join. The answer is `max(with[root], without[root])`, computed in one post-order pass, `O(n)` time and `O(height)` recursion space.

code

pseudocode · 15 lines
pseudocode
// score[v]    = seniority score of employee v
// children[v] = v's direct reports
// with[v]     = best subtree total, v ON the committee
// without[v]  = best subtree total, v OFF the committee
solve(v):
    take = score[v]
    skip = 0
    for c in children[v]:
        solve(c)
        take = take + without[c]
        skip = skip + max(with[c], without[c])
    with[v] = take
    without[v] = skip
...
answer = max(with[root], without[root])

go deeper

for a junior

Remember the shape: two numbers per node, one for 'this node is picked' and one for 'it is not', and the final answer is the larger of the two at the root.

for a middle

Explain both recurrences precisely — especially that the skipped case takes a max per child rather than forcing children in — and give the O(n) time and O(height) space.

for a senior

Show you can widen the state when the constraint changes: a larger forbidden radius, a cap on how many are picked, per-node costs under a budget, and what each does to time and memory.

for a principal

Judge whether the exact DP is even the right tool. Name the input sizes and constraint shapes where you would accept an approximation or a general solver, and what you would need to prove to justify that call.

## The setup Every employee in an org chart carries a seniority score. You want the highest-scoring committee subject to one rule: a manager and any of their direct reports may not both serve. The reporting structure is a tree, so this is the maximum-weight selection of nodes no two of which are adjacent. The greedy instinct — repeatedly take the highest remaining score and strike out its neighbours — fails, and it fails on tiny inputs. A chain of four with scores 4, 1, 1, 4 top to bottom: greedy takes a 4, strikes its neighbour, takes the other 4, and gets 8, which happens to be right here. Change it to 3, 4, 4, 3: greedy takes a 4 (say the second), strikes the first and third, then takes the last, for 7 — but taking both 3s and neither 4... is 6, worse. Try 1, 5, 5, 1: greedy takes a 5, kills the other 5's neighbour relationship, and gets 5 + 1 = 6, which equals the optimum. The reliable failure is a wider shape: a manager scoring 5 with two direct reports scoring 4 each and nothing else — greedy takes the 5 and stops, while the optimum takes both reports for 8. One locally attractive pick blocks two better ones. That is the general reason greedy is not safe on this constraint, and the reason a DP is the answer. ## Why one value per node is not enough Suppose each node returned a single number, "the best achievable inside my subtree". A parent reading that number cannot use it, because the parent does not yet know whether the child was picked in the plan that produced it. If the parent picks itself, only child plans that leave the child out are legal. The returned number has already collapsed the two cases and destroyed the distinction the parent depends on. That is the general lesson about DP state, not a trick specific to this problem: **the state must carry exactly the information the consumer of the subproblem needs.** Here the consumer is the parent, and the only thing it needs to know about a child's plan is whether the child itself was taken. So the state gains one binary dimension, and the answer per node becomes a pair. ## The recurrences - `with[v] = score[v] + sum over children c of without[c]` — picking `v` bars every direct report, so each child contributes its best plan that leaves the child out. - `without[v] = sum over children c of max(with[c], without[c])` — skipping `v` places no constraint on the children, so each child independently contributes whichever of its two plans is larger. Both are computed after all children are done, in a single bottom-up pass. The final answer is `max(with[root], without[root])`, because every employee lies in the root's subtree, so the two root plans between them cover every legal committee. The error that catches most candidates is writing `without[v] = sum of with[c]`. That reads the rule backwards: not choosing a manager does not require choosing their reports. It computes a legal but not-necessarily-optimal committee, so it silently under-reports on inputs where a child is better left off (a child with a small score and a very valuable grandchild is exactly that case). ## Cost Two values per node, constant work per parent-child link, `n-1` links: `O(n)` time. Storage is `O(n)` for the two arrays and `O(height)` for the recursion, which is `O(n)` on a deeply nested reporting line. If you also need the committee itself and not just its score, keep the pair of values and reconstruct downward from the root: at each node, having decided whether it is in, the children's decisions follow from the comparison you already made. ## Widening the state The pattern generalises the moment the rule changes, and interviewers push here: - **Forbid two picks within two levels.** The parent now needs to know more than "were you picked" — it needs "how close is your nearest picked node to you". Three states per node (picked here / picked at a child / nothing within two) instead of two. Time stays `O(n * states)`. - **Cap the committee at k people.** The state becomes a small table per node indexed by count, and merging child tables costs the product of their sizes — this is where the linear bound genuinely goes away. - **Costs as well as scores, under a budget.** Same shape as the cap, indexed by spend. The thing to notice across all three: the *traversal* never changes. What changes is the width of the state and, with it, the complexity. A candidate who can state "add a dimension to the state, keep the post-order" has understood the family rather than memorised one recurrence.

  • Why is the skipped case a max over each child rather than forcing every child in?
    Skipping a node only removes the constraint it would have imposed; it does not oblige the children to be taken. Each child is then free, so you take whichever of its two plans is larger. Forcing children in computes a legal but generally smaller total, and it loses every case where a child is worth leaving out to reach a more valuable grandchild.
  • How would you extend this to a rule that forbids picking two nodes within two levels of each other?
    Widen the state rather than change the traversal. Instead of a binary picked/not-picked flag, each node reports how close its nearest picked node is — picked here, picked at a child, or nothing within two levels. That is three values per node, still combined in one post-order pass, so the cost stays O(n * states).
  • Where does the final answer live in the tree?
    At the root. Every node lies inside the root's subtree, so max(with[root], without[root]) already ranges over every legal selection. That is a property of this objective, not of tree DP in general — objectives like a longest path attach to some internal node and must be tracked in a separate global best as the traversal unwinds.

It is like an invitation list where saying yes silently disinvites your immediate neighbours. Each person has to report two totals upward — best if I come, best if I stay home — because the person above them cannot choose until they know which.

saying these in an interview costs you the question

  • Returns one best value per node to the parent
  • Writes the skipped case as forcing all children in
  • Reaches for a greedy highest-score-first rule
  • Claims the adjacency rule needs a global visited set
  • Says the answer might be hiding in some subtree, not at the root

context

resolving links…