DP on Trees

Tree DP extends dynamic programming to tree structures. The key idea: the optimal answer at a node depends on the answers computed for its children. Post-order traversal (process children before parent) is the natural fill order, because every child's subproblem is solved before the parent needs its result.

Unlike grid DP where state transitions are always up/left, tree DP must handle a variable number of children and often returns multiple values from each subtree call to allow the parent to make its decision.

Diameter of Binary Tree

The diameter of a binary tree is the length of the longest path between any two nodes (the path may or may not pass through the root).

Key insight: For each node, the longest path through that node is: height(left subtree) + height(right subtree). The diameter is the maximum such value across all nodes.

Return two values per call: height (needed by parent) and local diameter (updated globally).

// Diameter of Binary Tree — O(n) time, O(h) space (h = tree height)
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function diameterOfBinaryTree(root) {
  let maxDiameter = 0;

  function height(node) {
    if (!node) return 0;

    const leftH  = height(node.left);
    const rightH = height(node.right);

    // Diameter through this node = leftH + rightH
    maxDiameter = Math.max(maxDiameter, leftH + rightH);

    // Return height of this subtree to parent
    return 1 + Math.max(leftH, rightH);
  }

  height(root);
  return maxDiameter;
}

// Build tree:      1
//                /   \
//               2     3
//              / \
//             4   5
const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3)
);
console.log(diameterOfBinaryTree(root)); // 3 (path: 4→2→1→3 or 5→2→1→3)

Maximum Path Sum

Find the path in the binary tree with the maximum sum (path can start and end at any node). Values can be negative.

Same pattern: For each node, the max gain it can contribute to a path coming from above is max(0, leftGain, rightGain) + node.val. The max path through this node = node.val + max(0, leftGain) + max(0, rightGain). But when returning to parent, we can only go one direction (not both).

// Binary Tree Maximum Path Sum — O(n) time
function maxPathSum(root) {
  let globalMax = -Infinity;

  function maxGain(node) {
    if (!node) return 0;

    // Only include child's contribution if it's positive
    const leftGain  = Math.max(0, maxGain(node.left));
    const rightGain = Math.max(0, maxGain(node.right));

    // Path through this node (can't be passed up further)
    const localPath = node.val + leftGain + rightGain;
    globalMax = Math.max(globalMax, localPath);

    // Return max gain if this node is included in a path going upward
    // (parent can only extend one branch)
    return node.val + Math.max(leftGain, rightGain);
  }

  maxGain(root);
  return globalMax;
}

// Tree: [-10, 9, 20, null, null, 15, 7]
const r2 = new TreeNode(-10,
  new TreeNode(9),
  new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
console.log(maxPathSum(r2)); // 42 (15→20→7)

Note

The pattern of "compute local answer, update global max, return something different to parent" is the core tree DP template. The local answer uses both children; the return value to parent uses only the better child.

House Robber III

Houses are arranged in a binary tree. Adjacent nodes (parent-child) cannot both be robbed. Maximize the total amount robbed.

State per node: two values — (rob this node, skip this node)

rob(node) = node.val + skip(left) + skip(right)
skip(node) = max(rob(left), skip(left)) + max(rob(right), skip(right))

// House Robber III — O(n) time, O(h) space
function rob3(root) {
  // Returns [robThis, skipThis]
  function dp(node) {
    if (!node) return [0, 0];

    const [robLeft,  skipLeft]  = dp(node.left);
    const [robRight, skipRight] = dp(node.right);

    // If we rob this node, children must be skipped
    const robThis  = node.val + skipLeft + skipRight;

    // If we skip this node, children can be robbed OR skipped (take the best)
    const skipThis = Math.max(robLeft, skipLeft) + Math.max(robRight, skipRight);

    return [robThis, skipThis];
  }

  const [robRoot, skipRoot] = dp(root);
  return Math.max(robRoot, skipRoot);
}

// Tree:   3
//        / \
//       2   3
//        \   \
//         3   1
const r3 = new TreeNode(3,
  new TreeNode(2, null, new TreeNode(3)),
  new TreeNode(3, null, new TreeNode(1))
);
console.log(rob3(r3)); // 7 (rob 3, skip 2 and 3, rob 3 and 1 → 3+3+1=7)

Tip

Returning a pair from each recursion call is the key trick for tree DP problems with include/exclude decisions. It avoids recomputing states and is naturally memoized by the call structure.

Binary Tree Cameras

Place cameras on nodes to monitor the entire tree. A camera at a node covers the node, its parent, and its children. Find the minimum number of cameras needed.

Greedy + Tree DP: Process leaves first (post-order). Place cameras as high as possible to cover as many nodes as possible. Three states per node:

0 = not covered (needs a camera from parent)
1 = covered (no camera here)
2 = has a camera

// Binary Tree Cameras — O(n) time
function minCameraCover(root) {
  let cameras = 0;

  // Returns:
  //   0 = this node is NOT covered (parent must place a camera)
  //   1 = this node is covered (no camera here)
  //   2 = this node has a camera
  function dp(node) {
    if (!node) return 1;  // null nodes are "covered" by default

    const left  = dp(node.left);
    const right = dp(node.right);

    // If either child is uncovered, must place camera here
    if (left === 0 || right === 0) {
      cameras++;
      return 2;
    }

    // If either child has a camera, this node is covered
    if (left === 2 || right === 2) return 1;

    // Both children are covered (no camera on them)
    // This node is uncovered — ask parent to cover us
    return 0;
  }

  // If root itself ends up uncovered, place a camera there
  if (dp(root) === 0) cameras++;

  return cameras;
}

// Tree: [0,0,null,0,0]
const r4 = new TreeNode(0,
  new TreeNode(0, new TreeNode(0), new TreeNode(0)),
  null
);
console.log(minCameraCover(r4)); // 1

Rerooting Technique

Standard tree DP roots the tree at node 0 and processes subtrees. But some problems ask for the answer at every node as root, or depend on the path going upward through the parent.

Rerooting (two-pass technique):

First DFS (bottom-up): Compute dp[v] assuming v is in a subtree (ignores parent direction)
Second DFS (top-down): Pass down contributions from the parent's direction, combining with the bottom-up results to get the full answer for each node as root.

// Sum of Distances in Tree — O(n) with rerooting
// For each node, return the sum of distances to all other nodes
function sumOfDistancesInTree(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }

  const count = new Array(n).fill(1);  // count[v] = subtree size rooted at v
  const ans   = new Array(n).fill(0);  // ans[v]   = sum of distances from v

  // Pass 1: DFS from root 0, compute count and ans[0]
  function dfs1(node, parent) {
    for (const child of adj[node]) {
      if (child === parent) continue;
      dfs1(child, node);
      count[node] += count[child];
      ans[node] += ans[child] + count[child];
      // Every node in child's subtree is 1 step farther from node
    }
  }

  // Pass 2: top-down, reroot to get ans for all nodes
  function dfs2(node, parent) {
    for (const child of adj[node]) {
      if (child === parent) continue;
      // When we reroot from node to child:
      //   count[child] nodes get 1 closer  (they were below child, now child is root)
      //   n - count[child] nodes get 1 farther (they were above child)
      ans[child] = ans[node] - count[child] + (n - count[child]);
      dfs2(child, node);
    }
  }

  dfs1(0, -1);
  dfs2(0, -1);
  return ans;
}

console.log(sumOfDistancesInTree(6, [[0,1],[0,2],[2,3],[2,4],[2,5]]));
// [8, 12, 6, 10, 10, 10]

Tree DP Pattern Summary

Problem	Return from subtree	Global update	Time
Diameter	Height of subtree	leftH + rightH	O(n)
Max Path Sum	Max gain from subtree	val + leftGain + rightGain	O(n)
House Robber III	[rob, skip] pair	max(rob, skip)	O(n)
Tree Cameras	Coverage state (0/1/2)	Place camera if child uncovered	O(n)
Sum of Distances	Count + sum	Reroot: pass parent info down	O(n)

Post-order DFS is the natural traversal order for tree DP
Return multiple values from subtree calls when parent needs different info
Use a global variable (closure or reference) for the actual answer when the best path crosses a node
The "return to parent" value is often different from the "local answer"
Rerooting solves problems that require considering all nodes as the root in O(n)