Tree DP — dynamic programming on trees

1 · Why tree DP is just array DP on a tree

Array DP requires you to invent an ordering. "What's the subproblem indexed by i? Do we go left-to-right or right-to-left? Is the recurrence dp[i] = f(dp[i-1]) or dp[i] = max(dp[j] for j < i)?" Half the difficulty of array DP is choosing the right state.

Trees are different. The ordering is given to you — the parent-child structure is the topological order. The DP transition is almost always one of two shapes: "compute my answer using my children's answers" (post-order), or "compute my answer using my parent's answer" (pre-order, for re-rooting). Most tree-DP problems are a single post-order DFS — the entire algorithm fits on a napkin.

The discipline that distinguishes a senior tree-DP answer: knowing the difference between what the helper returns up to the parent and what gets recorded as the global answer. Conflate them and you write the diameter bug everyone writes once. Keep them separate and every tree-DP problem turns into a fill- in-the-blank: decide the return type, decide the global, write the combine step.

Where tree DP shows up in real systems

• HTML / DOM layout engines. Computing the rendered height of a DOM tree is tree DP: each element's height depends on its children's heights. Browsers do exactly one post-order pass during reflow.
• Filesystem disk-usage tools (du). "Total size of a directory" = sum of file sizes in the subtree. Pure tree DP, executed lazily as you stat each subdirectory.
• Compiler register allocation (Sethi-Ullman). Number the nodes of an expression tree with the minimum number of registers needed to evaluate the subtree. A textbook tree DP from the 1970s; still used in code-generation passes.
• Ad-targeting trees in adtech. Hierarchical categorisation of users / contexts; each node aggregates child counts and conversion rates. Tree DP recomputes per-node aggregates after each batch update.
• Game AI minimax search. Each game-tree node returns the best score achievable from this position; the parent picks max or min depending on whose turn it is. Pure tree DP with alpha-beta pruning layered on top.

2 · How to recognise it

Tree DP is the right pattern when the input is a tree and the answer at each node is some function of its subtree. The signals overlap; any one or two is usually enough.

• The input is a tree. Binary tree, n-ary tree, or rooted forest. If it's a general graph you're closer to graph DP or DFS — trees are the special case with no cycles and a clear parent–child direction.
• Each node has a "best / worst / sum" that depends on its subtree. Height, diameter, max path sum, count of matching subtrees. If you can phrase the answer as "f(node) = combine(f(child) for child in node.children)", it's tree DP.
• Post-order traversal is the natural fit. You can't decide the parent until you know the children. Recurse first, combine after.
• The helper wants to return a tuple. When one number isn't enough — "best path ending at this node" and "best path passing through this node" are different things — the helper returns multiple summaries per subtree.
• The global answer differs from the return value. The answer is often "best over all nodes", updated as a side effect, while the return value is "best ending at this node" so the parent can extend it.

Recognition checklist — six shapes

• "Diameter of tree" flavour. Longest path between any two nodes — measured in edges or in node-value sum. Helper returns depth-from-this-node; global tracks the through-this-node path. LC 543, LC 124, LC 687.
• "Longest path through node N" flavour. Stricter than diameter — for every node, what's the longest path that bends at it? Same shape, but the answer is per-node rather than global. LC 1372 (longest ZigZag).
• "Subtree summary" flavour. Compute sum, count, min, max, or average across each subtree. Often a one-number return; sometimes a small object. LC 508 (most frequent subtree sum), LC 1120 (max average subtree).
• "Re-rooting / sum-of-distances-from-each-node" flavour. Asks for the answer at every node as if it were the root. Naive O(n²) becomes O(n) with the two-pass re-rooting trick. LC 834, LC 310.
• "Tree partition" flavour. Split the tree into K subtrees subject to some constraint (max-of-mins, min-of-maxes). Combines tree DP with binary search on the answer. LC 1339 (max product split), LC 124 with a twist.
• "Path queries on a tree" flavour. Heavy use of path information (sum, max, GCD) between arbitrary pairs of nodes — usually solved with heavy-light decomposition + segment tree, or Euler tour + sparse table for LCA. Senior systems-design crossover.

3 · Intuition — every tree-DP problem is one of three shapes

Boil tree DP down to its essential variants and three shapes cover 95% of LeetCode hard problems. Recognising which one you're looking at is half the battle.

Shape A — "answer at node = combine children's answers"

The simplest case. Each node's answer is a pure function of its children's answers; the global answer is the root's value. No side channel needed. Examples: max depth of binary tree (LC 104), sum of all subtree values, count of nodes matching some predicate.

// Max depth — the canonical Shape A
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}

Shape B — "return one value, track another"

Tree diameter (LC 543) is the exemplar. The helper returns depth (what the parent needs to extend its own path), but tracks diameter (what's not extendable upwards — a path that bends at this node uses BOTH children). Two values; only one is returned; the other lives in a closure or class variable.

// Diameter — the canonical Shape B
func diameterOfBinaryTree(root *TreeNode) int {
    best := 0
    var depth func(n *TreeNode) int
    depth = func(n *TreeNode) int {
        if n == nil {
            return 0
        }
        lh := depth(n.Left)
        rh := depth(n.Right)
        if lh+rh > best {
            best = lh + rh  // tracked, not returned
        }
        return 1 + max(lh, rh) // returned, not tracked
    }
    depth(root)
    return best
}

Shape C — "re-rooting" (answer for every node as if it were root)

The hardest shape. Some problems ask "for every node v, what's the answer if v were the root?" — sum of distances from v to all others, longest path from v, etc. Naive: run tree DP from every node, O(n²). The re-rooting trick reduces this to O(n) by doing two passes — first compute down-subtree info from an arbitrary root, then a top-down pass to compute "what would the rest of the tree look like if I flipped the parent edge". LC 834 is the canonical example.

4 · Canonical example — Diameter of Binary Tree (LC 543)

Problem. Given the root of a binary tree, return the length of the diameter — the longest path between any two nodes, measured in edges. The path may or may not pass through the root.

Input:        1
             / \
            2   3
           / \
          4   5
Output: 3
Explanation: 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3), length 3 edges.

For each node, compute the height of its left and right subtrees. The longest path that passes through this node has length leftHeight + rightHeight. The longest path overall is the maximum of that quantity across every node. The helper returns height (what the parent needs to extend the path); the diameter is tracked as a running maximum on the side. Time O(n), space O(h) for the recursion stack.

5 · Reference implementation

class Solution:
    def diameterOfBinaryTree(self, root) -> int:
        self.best = 0

        def height(node) -> int:
            if not node:
                return 0
            lh = height(node.left)
            rh = height(node.right)
            # path THROUGH this node uses both children
            self.best = max(self.best, lh + rh)
            # path FROM this node up uses only the taller child
            return 1 + max(lh, rh)

        height(root)
        return self.best

The two lines marked through and from are the whole pattern. The first updates the global answer. The second is what the parent sees — it can only extend the path through one child, not both. Mixing them up is the most common bug.

The same shape, with a sign-handling twist, solves Max Path Sum (LC 124). Negative subtree contributions should be clamped to zero before extending.

class Solution:
    def maxPathSum(self, root) -> int:
        self.best = float('-inf')

        def gain(node) -> int:
            if not node:
                return 0
            # clamp: a child only contributes if it helps
            left  = max(0, gain(node.left))
            right = max(0, gain(node.right))
            # path through this node combines both children
            self.best = max(self.best, node.val + left + right)
            # path returned upward uses one child only
            return node.val + max(left, right)

        gain(root)
        return self.best

6 · Sister algorithms

Tree DP doesn't stop at "one post-order DFS". When the problem asks "for every node" or "across millions of path queries", a small family of techniques takes over. Knowing the names is the senior- interview depth check.

• Re-rooting technique. Computes the answer for every node as if it were the root in O(n) instead of O(n²). Two passes: post-order to compute down-subtree info from an arbitrary root, then a pre-order top-down propagation. LC 834 (Sum of Distances in Tree) is the canonical exam.
• Heavy-light decomposition (HLD). Splits the tree into a set of vertex-disjoint paths so any root-to-node path crosses O(log n) of them. Combined with a segment tree per path, supports path queries (sum, max, GCD) and path updates in O(log² n) each. Showed up at the Bloomberg / quant level; rare in product interviews, common in CP.
• Euler tour + sparse table for LCA. Flatten the tree by walking it in Euler order; LCA(u, v) becomes "range minimum on depths" between u's and v's first occurrences. Preprocessing O(n log n), queries O(1) with a sparse table. The standard offline solution for billions of LCA queries.
• Binary lifting (jump pointers). Each node stores its 2^k-th ancestor for k = 0, 1, 2, ... Answers "kth ancestor" in O(log n) and LCA in O(log n) too. Used in dynamic-LCA situations and competitive programming.
• Centroid decomposition. Recursively split the tree at its centroid (node whose removal leaves subtrees of size ≤ n/2). Many "count paths satisfying property P" problems become tractable: count paths through the centroid (cheap), recurse on each subtree. Total O(n log n).
• Small-to-large merging on trees. When each subtree carries a set or multiset and you need to merge children into the parent's collection, always merge the smaller into the larger. Total work across all merges: O(n log n). Used in "distinct values in subtree" problems (LC 1339 cousins).
• Auxiliary tree / virtual tree. Given K query nodes in a tree, build a minimal contraction that contains only those nodes and their LCAs. Useful when you need to answer many "what subset of marked nodes" questions efficiently.

7 · Variations

What changes between tree DP problems is what the helper returns and how many states each node tracks. Five common shapes:

7a · "Return one, track another" on a tree

Diameter (LC 543) is the cleanest example of the tree-DP idiom. Each node's recursion call returns DEPTH (one number the parent uses), and updates a closure variable that tracks the global DIAMETER (the other answer, computed at this node but unusable upstream). Watch a 7-node tree get evaluated bottom-up:

8 · Five-problem progression

8a · The mental model — post-order is the engine

Every tree-DP solution has the same shape. Post-order traversal: visit children first, then process the current node using results from its children. The return value from each subtree is whatever the parent needs to compute its own answer. That is the entire pattern.

Three questions to ask at every node:

1. What does my parent need from me? A single number (height, sum)? A tuple (best-with-this-node, best-without)? An object (multiple summary statistics)? The answer to this is the return type of the recursive function.

2. What do I compute using my children's returns? Sum them? Take the max? Combine them in some custom way? This is the body of the post-order step.

3. What might I contribute to the global answer at this node? This is where you update the outer answer variable — typically a path-through-this-node calculation that the parent does not need but that might be the global maximum.

Whenever you write a tree-DP, write down the answers to these three questions before writing code. Most tree-DP bugs come from conflating answer 1 (what the parent needs) with answer 3 (the global maximum). They are different; tracking them separately is the discipline.

8b · The state-tuple trick — when one number is not enough

Many tree-DP problems have the shape "a node's choice affects what its parent can do". House Robber III is canonical: if a node is robbed, its parent cannot be. The clean expression is to return two values per node: (best-if-robbed, best-if-not-robbed). The parent then computes its own two values from the children's tuples.

12345678910111213

def rob(root):
    def helper(node):
        if not node:
            return (0, 0)   # (rob_here, dont_rob_here)
        l_rob, l_skip = helper(node.left)
        r_rob, r_skip = helper(node.right)
        # If we rob this node, children must skip
        rob_here = node.val + l_skip + r_skip
        # If we skip, children can do whichever is better
        skip_here = max(l_rob, l_skip) + max(r_rob, r_skip)
        return (rob_here, skip_here)

    return max(helper(root))

The state tuple pattern generalises. Maximum-Independent-Set on a tree, Minimum-Vertex- Cover, Tree-Coloring, "longest sequence with at most K of X" — all have the same shape: the node's choice creates a small set of states; return one value per state; combine in the parent.

Rule of thumb: if you find yourself doing "best max(rob_left, skip_left) + best max(rob_right, skip_right)" anywhere, you have lost information by collapsing the tuple too early. Push the max into the parent's computation, not the child's return.

8c · Re-rooting — when every node is the answer

Some tree problems ask "for every node, what is the answer if we root the tree there" rather than "what is the global answer". Re-rooting (a.k.a. rerooting DP, or "DP on trees with all-roots") is the technique.

The naive solution runs tree-DP from every possible root: O(N²). Re-rooting reduces this to O(N) by doing two traversals:

Pass 1: bottom-up DP from an arbitrary root. Compute down[v] = the answer in the subtree rooted at v.

Pass 2: top-down propagation. Compute up[v] = the answer if we "flip" the tree and root it at v. Each child gets its up value from the parent's up plus the parent's down minus its own contribution to the parent's down.

Combining up[v] and down[v] gives the answer rooted at v for every v in O(1) per node.

1234567891011121314151617181920212223242526

def reroot(adj, n):
    down = [0] * n
    up   = [0] * n
    ans  = [0] * n

    # Pass 1: post-order from root 0
    def dfs_down(u, parent):
        for v in adj[u]:
            if v != parent:
                dfs_down(v, u)
                down[u] += down[v] + 1   # +1 for the edge (u,v)

    # Pass 2: pre-order propagation
    def dfs_up(u, parent):
        for v in adj[u]:
            if v != parent:
                # u's answer minus v's subtree contribution = "rest"
                rest = (down[u] - (down[v] + 1)) + up[u]
                up[v] = rest + 1
                dfs_up(v, u)

    dfs_down(0, -1)
    dfs_up(0, -1)
    for u in range(n):
        ans[u] = down[u] + up[u]
    return ans

Classic re-rooting problems: Sum of Distances in Tree (LC 834), Tree Distances on Codeforces, Minimum Height Trees (LC 310 has a different solution but re-rooting works), Best subtree sum from every node. Once you recognise the shape — "for every possible root, compute X" — re-rooting is the answer.

8d · Tree knapsack — adding a budget dimension

Tree knapsack problems combine tree-DP with a knapsack constraint: each node has a cost and value; you must pick at most K nodes total; subject to some tree constraint (say, picking a node requires picking its parent — the "dependent items knapsack"). Examples: Cherry Pickup II, Selecting Courses with Prerequisites, Maximum Profit in Job Scheduling with hierarchy.

The state per node becomes (node, k) where k is the budget remaining. The transition combines children's DP tables via a knapsack-merge: for the current node's table at budget k, sum the best ways to split k between the children's tables.

Complexity is the surprise: a naive analysis suggests O(N × K²) per node, but the careful analysis ("tree knapsack lemma") shows the total work is actually O(N × K). The trick is that the inner loop iterates over min(subtree_size, K) — and summing min(subtree_size, K) across the tree telescopes to O(N + N×K/N × K) = O(N×K) total.

The proof comes up in competitive programming circles; the practical takeaway is that tree knapsack is faster than it looks, and a clean implementation that runs through children sequentially performs well even for N = 10⁴, K = 100.

9 · Three worked problems — return-vs-track at three difficulty levels

Three tree-DP problems that look nothing alike but use the same "return one, track another" backbone. The middle one (LC 968) introduces a state machine — three states per node, post-order rule. The hardest one (LC 834) is the re-rooting exemplar.

9a · LC 124 — Binary Tree Maximum Path Sum

Problem. Given the root of a binary tree, return the maximum sum of values along any path (a sequence of adjacent nodes). The path doesn't have to pass through the root.

Input:        -10
              /  \
             9    20
                 /  \
                15   7
Output: 42
Explanation: 15 → 20 → 7 = 42. The root contributes negatively, so skip it.

The canonical "return one, track another" with a sign-handling twist. The helper returns the best downward path-sum from this node (one child only, clamped to 0 — if both children are negative, skip them entirely). The global tracks the best path that bends at this node, which uses both children.

func maxPathSum(root *TreeNode) int {
    best := math.MinInt32

    var gain func(n *TreeNode) int
    gain = func(n *TreeNode) int {
        if n == nil {
            return 0
        }
        // CLAMP: a child only contributes if it helps
        left := max(0, gain(n.Left))
        right := max(0, gain(n.Right))

        // Path that BENDS at this node uses both children
        through := n.Val + left + right
        if through > best {
            best = through
        }

        // Path EXTENDABLE up uses one child only
        return n.Val + max(left, right)
    }

    gain(root)
    return best
}

9b · LC 968 — Binary Tree Cameras

Problem. Install cameras on tree nodes; each camera monitors its parent, itself, and immediate children. Find the minimum number of cameras to cover all nodes.

Input:       0
            / \
           0   0
          / \
         0   0
Output: 2
Explanation: Place cameras on the two interior nodes. Each covers parent and children.

Classic three-state tree DP. Each node returns one of three states:

• State 0: this node NEEDS a camera (it's not yet covered).
• State 1: this node HAS a camera (so it covers itself + parent + children).
• State 2: this node is COVERED by a child's camera (so it's safe but doesn't cover its parent).

Post-order rule. Leaves return state 2 (covered — by lying that a "null camera" exists). At any internal node, look at children's states:

• Any child returned state 0 (needs camera) → install here, return state 1. A node with an uncovered child must install a camera.
• Else if any child returned state 1 (has camera) → return state 2 (covered). A camera on a child covers this node.
• Else (all children returned state 2) → return state 0 (needs). No camera below; this node is uncovered.

const (
    NEEDS   = 0
    HAS     = 1
    COVERED = 2
)

func minCameraCover(root *TreeNode) int {
    cameras := 0

    var dfs func(n *TreeNode) int
    dfs = func(n *TreeNode) int {
        if n == nil {
            return COVERED // null is harmlessly "covered"
        }
        l := dfs(n.Left)
        r := dfs(n.Right)

        if l == NEEDS || r == NEEDS {
            cameras++
            return HAS
        }
        if l == HAS || r == HAS {
            return COVERED
        }
        return NEEDS
    }

    if dfs(root) == NEEDS {
        cameras++ // root still uncovered — install one
    }
    return cameras
}

9c · LC 834 — Sum of Distances in Tree (HARD)

Problem. An undirected tree with n nodes. For each node, return the sum of distances from it to all other nodes. Output: an array of length n.

Input:  n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8, 12, 6, 10, 10, 10]

Tree:        0
            / \
           1   2
              /|\
             3 4 5

For node 0: distance to {1,2,3,4,5} = {1,1,2,2,2} = 8.
For node 2: distance to {0,1,3,4,5} = {1,2,1,1,1} = 6. And so on.

The re-rooting exemplar. Naive — run BFS from every node — is O(n²). The trick: compute the answer at node 0 normally, then propagate to every other node in O(1) per child using a key identity. If node u is the current root and v is u's child, then moving the root from u to v shifts every node in v's subtree one closer to the new root, and every other node one farther.

Concretely, let count[v] = number of nodes in v's subtree (rooted at 0), and ans[u] = sum of distances from u. Then:

ans[v] = ans[u] - count[v] + (n - count[v])
       = ans[u] + n - 2*count[v]

Two DFS passes. Pass 1 (post-order from 0): compute count[v] and ans[0]. Pass 2 (pre-order from 0): compute ans[v] from ans[parent] using the identity above.

func sumOfDistancesInTree(n int, edges [][]int) []int {
    adj := make([][]int, n)
    for _, e := range edges {
        adj[e[0]] = append(adj[e[0]], e[1])
        adj[e[1]] = append(adj[e[1]], e[0])
    }
    count := make([]int, n)
    ans := make([]int, n)

    // Pass 1: post-order from 0
    // Compute count[v] (subtree size) and ans[0] (sum of depths)
    var dfs1 func(u, parent, depth int)
    dfs1 = func(u, parent, depth int) {
        count[u] = 1
        ans[0] += depth
        for _, v := range adj[u] {
            if v != parent {
                dfs1(v, u, depth+1)
                count[u] += count[v]
            }
        }
    }
    dfs1(0, -1, 0)

    // Pass 2: pre-order — propagate ans down using the identity
    var dfs2 func(u, parent int)
    dfs2 = func(u, parent int) {
        for _, v := range adj[u] {
            if v != parent {
                // Re-root from u to v: nodes in v's subtree get closer (count[v]),
                // all others get farther (n - count[v])
                ans[v] = ans[u] + n - 2*count[v]
                dfs2(v, u)
            }
        }
    }
    dfs2(0, -1)

    return ans
}

10 · How to solve hard tree DP problems step-by-step

Five questions to walk through, in order, on any tree-DP problem. Spend two minutes on these before writing any code; the implementation almost always falls out.

1. Write the brute force for any single node. "What's the answer if I were the only node in question?" — that's the DP value to compute. For diameter: "longest path passing through me". For House Robber III: "max money in my subtree given I rob/skip myself".
2. Decide if you return one value or multiple. One value: the parent only needs to know one thing about each child. Multiple (a tuple, or named states): the parent needs to combine choices, like in House Robber where rob/skip-current depends on rob/skip-child.
3. Decide what "answer for the whole tree" is. Two flavours. (a) Root's value (House Robber III: max(helper(root))). (b) Max/sum/min over all nodes, tracked as a side effect (Diameter, Max Path Sum). Identify which case before writing the helper.
4. If "answer for each node as if it's root" → re-rooting. The signal is "output an array of length n where ans[v] depends on v's perspective of the tree". Two passes — post-order to gather subtree info, pre-order to propagate. Spend the extra 20 lines.
5. Draw 3-5 small trees and trace by hand. Single node. Two-node path. Three-node star. Three-node path. Five-node skewed. Each catches a different edge case. If your code gives the right answer on all five, it's almost certainly correct on big inputs.

11 · Re-rooting walkthrough — visualised

Re-rooting is the technique most candidates fumble in interviews. One picture is worth the words: here's the LC 834 two-pass computation on a six-node tree.

12 · Common pitfalls

• Confusing return value with global answer. The return value is what the parent gets from a child; the global answer is what you report at the end. They're rarely the same. Diameter returns height, answers the diameter. Max path sum returns "best ending here", answers "best anywhere".
• Path "through" vs path "from". A path through a node uses both children's heights summed. A path from a node uses only the larger child. Treating them the same is the diameter bug everyone writes once.
• Returning the wrong subset of state. In House Robber III, returning only "max(rob, no-rob)" loses information — the parent needs both, because if it robs itself the child must be no-rob. Tuple returns exist for a reason.
• Forgetting the "use this node" vs "skip this node" split. Whenever a node's choice constrains the parent, you need at least two states per node. Single-value returns collapse the cases and silently produce wrong answers on small inputs.
• Recursion depth on skewed trees. A right-leaning chain of 10⁴ nodes blows Python's default recursion limit (1000). Either sys.setrecursionlimit(20000), convert to an iterative post-order with an explicit stack, or rely on the problem setter to bound depth.
• Not memoising when subtrees can repeat. On a true tree (each node has one parent) memoisation is unnecessary — each node is visited once. On a DAG masquerading as a tree, or on tree-knapsack-style problems where the state is (node, k), add memoisation.
• Not handling null children. The base case of most tree DPs is "if node is nil, return identity-of-combine" (0 for sum, -∞ for max, true for AND, false for OR). Forgetting this nil check is the #1 nil-pointer panic in tree-DP Go code. Always start the helper with a nil guard.
• Mixing up pre-order and post-order. Tree DP almost always wants post-order — you can't compute the parent's answer until you know the children's. If you find yourself using self.global before recursing, you're in pre-order and the result depends on traversal order. Suspect bug.
• Double-counting subtree contributions in re-rooting. When you compute ans[v] = ans[u] + n - 2*count[v], the count[v] is "size of v's subtree when rooted at the OLD root u". Easy to mistakenly use a fresh count or a per-current-root count. Always derive your propagation identity carefully on a 4-node tree before scaling.
• Forgetting to propagate state up the recursion. In multi-state problems (LC 968 cameras), the parent's decision depends on what every child returned. Returning "covered" when the child actually has a camera (or vice versa) silently doubles the camera count.
• Iterative tree DP via explicit stack: forgetting the "visited" flag. Iterative post-order needs a marker indicating whether you've already recursed into children. Pushing the node twice (with and without a sentinel), or using a colour set, is the standard fix. Skipping it makes the loop process the same node twice with wrong children-results.

13 · What to say in the interview

1. "Tree problem where children inform the parent — tree DP." Name it out loud. The interviewer wants to hear you spot the shape.
2. "Post-order DFS." Recurse into the children first, combine their answers at the node.
3. "The helper returns what the parent needs." Be explicit about the return type. "Height" or "max sum ending here" or "(rob, no-rob)".
4. "The global answer is updated as a side effect." Distinguish it from the return value. Walk through one node by hand if the interviewer looks unsure.
5. "Each node visited once, so O(n) time, O(h) stack space." State both. Mention skewed trees push h to n.
6. Edge cases. Empty tree, single node, negative values (for sum-style problems), heavily skewed trees and the recursion limit.

14 · Where this gets asked

15 · Try it yourself

Diameter of Binary Tree · LC 543

The cleanest "return one, track another". Hint: helper returns DEPTH (left + right + 1 of children); track max_diameter = max(max_diameter, left_depth + right_depth) at each node. Don't try to return the diameter directly — the parent can't use it.

House Robber III · LC 337

The tuple-return classic. Hint: helper returns (rob_this, skip_this). rob_this = node.val + left.skip + right.skip; skip_this = max(left) + max(right). Answer at root is max(rob, skip).

Binary Tree Maximum Path Sum · LC 124

The masterclass. Hint: helper returns the best DOWNWARD gain (one side only, clipped to 0). Track the global max of node.val + left_gain + right_gain at each node — that's the path that bends at this node, which the parent can't use.

Path Sum III · LC 437

Tree DP + prefix-sum trick. Hint: DFS while carrying a running sum and a hash of prefix-sum counts on the current root-to-node path. Path with sum k from ancestor A to current = running_sum - prefix_sums[A] = k. Don't forget to decrement the hash on the way back up.

Stretch — Binary Tree Cameras · LC 968

Three-state tree DP. Hint: each node returns one of {needs-camera, has-camera, covered-by-child}. Post-order. If any child needs-camera → install here (counts++). If any child has-camera → covered. Else needs-camera. Root edge-case: if it needs-camera at end, install one.

Further reading

• CLRS — Chapter 15 (Dynamic Programming). The textbook DP intro. Tree DP isn't called out by name but the optimal-substructure framing is the foundation.
• Adjacent: Recursion. Tree DP is recursion with a return value that carries information. If recursion still feels shaky, start there.
• Adjacent: DFS. Plain DFS visits and acts; tree DP visits and then combines what the recursion returned. Same skeleton, different intent.
• Adjacent: Dynamic programming. The broader pattern. Tree DP is the case where the subproblem graph happens to be a tree.
• Semicolony: Balanced-tree simulator. Worth a few minutes to see how heights, subtree counts, and rotations behave — the same quantities tree DP helpers return.