Tree Dynamic Programming Interview Questions: Subtree States and Global Answers

Tree dynamic programming interview questions become simpler when you separate two ideas that often get merged: the value a subtree returns to its parent, and the best answer found anywhere in the whole tree. In a diameter problem, a parent can extend only one downward path, but the best path at a node may join two children. In an independent-set problem, a parent needs two states from each child because choosing one endpoint constrains the other. Define those contracts before writing DFS.

The question-bank exercise is practice, not a claim about your next interview. The trees, recurrences, and tests here are original teaching examples grounded in official problem statements.

Ask what information a parent actually needs

A tree DP state is a compact summary of a subtree that is sufficient for the rest of the computation. “The answer below this node” is often too vague. State whether the value must include the current node, whether it can end anywhere, what unit it uses, and which decisions made above the subtree constrain it. That sentence determines the recurrence.

For diameter, define height(u) as the maximum number of edges on a downward path starting at u and ending in its subtree. A parent can extend one such path through u; it cannot extend two branches through the same child and remain a simple path. Separately, best records the largest diameter candidate seen at any node. For an empty child, choose a convention such as height -1, so a leaf has height 0.

For a selected-node problem, the state may be two numbers: take(u) and skip(u). Each is an optimum over the subtree under a specified choice at u. A single unconstrained optimum loses the information a parent needs to avoid selecting adjacent nodes.

Derive diameter with a return value and a global answer

The LeetCode diameter problem defines a longest path between two nodes, counted in edges, and the path need not pass through the root. At node u, let the two largest child heights be h1 and h2. With empty child heights -1, the downward height returned to the parent is 1 + max(h1, h2). The best path that bends at u is h1 + h2 + 2. Update the global answer with that candidate.

For a binary tree those are simply left and right heights. In an n-ary tree, scan children for the two largest heights. A common wrong answer returns h1 + h2 + 2 to the parent. That value is a complete path with two ends; extending it upward through the parent would create a fork rather than a simple path.

Trace an asymmetric tree: root R has child A and child B. A has descendants along one chain A1 -> A2, while B has one leaf B1. The deepest path is A2-A1-A-R-B-B1, five edges. At A1, return height 1 to A; at A, return 2 to R. At B, return 1. At R, the crossing candidate is 2 + 1 + 2 = 5, while its return height is only 1 + max(2,1) = 3. If a deeper diameter lies entirely inside A, the best accumulator keeps it even when the root's crossing candidate is smaller.

The algorithm visits each node once, so time is O(n); recursion stack is O(h), where h is tree height. A chain of 100,000 nodes may exceed a language's recursion limit, so mention an iterative postorder traversal when constraints demand it. For an undirected tree, carry the parent ID (or visited set) to avoid walking back to the node you came from.

Compare maximum path sum without copying the formula

Binary Tree Maximum Path Sum looks similar, but its path is scored by node values, not edge count. If negative child gains are optional, the return value can be value(u) + max(0, leftGain, rightGain). The local through-node candidate is value(u) + max(0,leftGain) + max(0,rightGain). Initialize the global best to negative infinity, not zero, because an all-negative tree still has a nonempty path as its answer.

This contrast is a useful interview check. Diameter's empty-child convention and path-length units cannot be pasted into maximum path sum unchanged. In a tree with root -10 and children 9 and 20, a tempting “always join both” formula would be wrong if the best path sits under 20; the accumulator lets the best path be located anywhere. The exact optimum depends on the full child subtrees, so trace concrete values instead of citing a memorized template.

When explaining, identify three objects: the state sent upward, the local answer completed at this node, and the global combination rule. That vocabulary generalizes to camera placement, longest univalue path, and alive-node distance problems only after their own constraints are specified.

Use two states when adjacency matters

Consider a weighted independent set on a tree: select vertices with maximum total weight, but no edge may have both endpoints selected. For node u, define take(u) as the best total in its subtree when u is selected, and skip(u) when it is not. Then:

take(u) = weight(u) + sum(skip(v) for each child v)
skip(u) = sum(max(take(v), skip(v)) for each child v)
answer = max(take(root), skip(root))

If u is taken, each child must be skipped. If u is skipped, each child can choose its better valid state independently. That is the whole proof by induction on subtree height: assuming the child states represent optimal legal solutions, the parent recurrence enumerates exactly the legal parent-child choices without overlap.

Work a four-node example: root R has weight 4; children A and B weigh 5 and 3; A has child C weighing 6. At C, (take,skip)=(6,0). At A, (take,skip)=(5,6). At B, (3,0). At R, take=4+6+0=10, while skip=max(5,6)+max(3,0)=9; select R and C for 10. A greedy choice of the largest immediate child could miss that grandchild combination.

The AtCoder DP P Independent Set task asks for the number of valid black/white colorings where adjacent nodes cannot both be black, modulo a stated value. That is a different objective from maximum weight. Its analogous count states use multiplication across independent child subtrees and addition across alternatives: black(u)=product(white(v)), white(u)=product(black(v)+white(v)). The shape of the state contract survives; the algebra changes. Do not use max for a counting problem.

Distinguish subtree answers from global answers

Some problems return the final answer at the root because every valid solution decomposes under the root: the independent-set recurrence is one. Others need a separate best-over-all-nodes accumulator because the optimum path may start and end below the root: diameter and maximum path sum are examples. A third pattern returns a composite state whose root component gives the answer.

Ask yourself two diagnostic questions. Can the optimal object be wholly contained in one child subtree? Can it cross the current node using two children? If both are possible, a local crossing candidate plus a child/global best is usually needed. If a parent decision constrains the root of a child subtree, preserve separate states for those constrained cases.

Avoid using a global variable just because it is convenient. A pure DFS can return {height, bestDiameter} and combine child best values with the crossing candidate; this may be easier to test or parallelize. The important separation is conceptual, not the storage location. State the chosen representation and its invariant.

Verify recurrences with a tiny exhaustive oracle

An interview-sized oracle should be slow but unquestionably direct. For a weighted independent set with at most ten nodes, enumerate all 2^n subsets, reject any subset containing both endpoints of an edge, and record the maximum weight. Compare that number with the DP on randomly generated small trees. This catches a missing skip branch faster than more hand-picked happy paths.

For diameter, enumerate all node pairs in a tiny tree and measure their unique-path distance with breadth-first search. Compare the maximum with the DFS result. Test one node (diameter 0), a chain (n-1), a star (diameter 2 for at least two leaves), and an asymmetric tree where the best path does not pass through the chosen root. Verify whether the question counts edges or nodes; an off-by-one error often comes from changing conventions mid-solution.

If you have only minutes, write assertions for the leaf and the asymmetric case before coding the optimized version. Explain that brute force is a validator, not the submitted large-input algorithm. It supplies an independent definition of the answer and makes randomized differential testing possible afterward.

Handle roots, negatives, and representation details

An undirected tree is commonly supplied as edge pairs, so build adjacency lists, pick any root, and carry parent in DFS. The mathematical answer should be root-independent. If rerooting changes it, inspect whether you accidentally excluded a branch or counted the parent as a child.

For weighted selections, clarify whether choosing no node is allowed. With negative weights, skip(root)=0 may legitimately beat every selection if the empty set is allowed. If the task requires at least one node, augment the state or use a negative-infinity impossible value; do not quietly return zero. For path sums, an empty path is usually not allowed, which is why global initialization matters.

For counts modulo M, reduce after multiplication/addition and use a numeric type large enough for intermediate products. For reconstruction, store which child decision achieved the state and walk down after computing the optimum. For a tie, define whether any valid solution is acceptable or a specific tie-break is required.

A concise interview explanation

Before writing code, say: “My DFS return value is exactly what the parent can extend. I compute any answer completed at this node separately and combine it with the best already inside children. If the parent's decision restricts this node, I return one state per restriction.” Then derive one leaf, one internal node, and the root answer. That explanation demonstrates why the recurrence is correct, not merely that you have memorized it.

Use Compute binary tree diameter to rehearse the one-branch-return/two-branch-answer distinction, then solve the independent-set variant on paper without looking at code. If you can explain why max, sum, and product appear in their respective recurrences, you can adapt to unfamiliar tree dynamic programming interview questions.

Sources and Further Reading

• LeetCode: Diameter of Binary Tree
• LeetCode: Binary Tree Maximum Path Sum
• AtCoder Educational DP Contest P: Independent Set

The numerical trees and oracle strategy are original practice examples.