Tree DP Interview Questions
Last updated 2026-11-19
Tree dynamic programming solves a problem on a tree by combining answers from the children of each node. The recursion visits every node once and returns a small summary, such as a pair of values or a tuple, that the parent uses. Many hard-looking tree questions reduce to choosing the right summary.
This page works through ten problems, each with Python and Java code, complexity and edge cases. For the basic recursion over trees see binary tree interview questions, and for the general method see dynamic programming interview questions. Traversal order variants are on tree traversal interview questions.
| Pattern | Post-order traversal returning a summary |
|---|---|
| Typical cost | O(n) time, O(h) space |
| Common summaries | Pairs, three states, tuples |
| Advanced | Rerooting for answers from every node |
The pattern and when to spot it
Think of tree DP when the answer for a node depends on choices in its subtree and those choices interact only through the node. Typical triggers are phrases such as maximum or minimum over the tree, no two adjacent, choose a set of nodes, longest path, or count the ways. The state is usually the node plus a small flag, such as taken or not taken, or one of a few coverage states.
Write down what each child returns, then how the parent combines the returns. For path problems the parent joins the two best child arms, while the value returned upwards uses only one arm. For all-nodes answers, such as the sum of distances, compute subtree facts bottom-up, then push results top-down in a second pass, an idea called rerooting. For graphs given as edge lists, pass the parent to avoid revisiting.
Common mistakes
- Returning the through-path value to the parent, when only a single arm can continue upward.
- Using a global answer and forgetting to reset it between test cases in Java.
- Treating a missing child as uncovered or negative instead of a neutral value.
- Recursing on a path graph with 10^5 nodes and hitting the stack limit.
- Mixing node counts and edge counts in lengths.
Tree DP Interview Questions: questions with worked answers
1 House robber III: loot a binary tree of houses
mediumRobbing a node forbids robbing its children. Return a pair from each call: the best loot if this node is robbed, and the best if it is skipped. Robbed = node + skipped(left) + skipped(right). Skipped = max of both options for each child, added up. The answer is the larger of the pair at the root. Time O(n), space O(h). Edge cases: empty tree (0), a single node, a chain where alternating nodes win, a naive recursion without pairs is exponential.
pythondef rob(root): def go(n): if not n: return (0, 0) # (robbed, skipped) l, r = go(n.left), go(n.right) robbed = n.val + l[1] + r[1] skipped = max(l) + max(r) return (robbed, skipped) return max(go(root))javaint rob(TreeNode root) { int[] r = go(root); return Math.max(r[0], r[1]); } private int[] go(TreeNode n) { // {robbed, skipped} if (n == null) return new int[]{0, 0}; int[] l = go(n.left), r = go(n.right); int robbed = n.val + l[1] + r[1]; int skipped = Math.max(l[0], l[1]) + Math.max(r[0], r[1]); return new int[]{robbed, skipped}; }2 Longest path of equal values in a binary tree
mediumEach call returns the longest downward path starting at the node that uses only nodes equal to its value, counted in edges. A child extends the path only if its value matches the node. At each node the best path through it joins the left and right arms. Update a global maximum with that sum. Time O(n), space O(h). Edge cases: empty tree (0), a single node (0 edges), a path that bends at a middle node, children with different values contributing 0.
pythondef longest_univalue_path(root): best = 0 def go(n): nonlocal best if not n: return 0 l, r = go(n.left), go(n.right) l = l + 1 if n.left and n.left.val == n.val else 0 r = r + 1 if n.right and n.right.val == n.val else 0 best = max(best, l + r) return max(l, r) go(root) return bestjavaint best; int longestUnivaluePath(TreeNode root) { best = 0; go(root); return best; } private int go(TreeNode n) { if (n == null) return 0; int l = go(n.left), r = go(n.right); l = n.left != null && n.left.val == n.val ? l + 1 : 0; r = n.right != null && n.right.val == n.val ? r + 1 : 0; best = Math.max(best, l + r); return Math.max(l, r); }3 Distribute coins in a binary tree so every node has one
mediumReturn the excess of each subtree: coins in it minus nodes in it. A positive excess must flow up through the edge to the parent, a negative one must flow down, and either way it costs its absolute value in moves. At each node excess = val - 1 + left excess + right excess, and the moves added are |left excess| + |right excess|. Time O(n), space O(h). Edge cases: the total number of coins equals the number of nodes by the statement, a single node (0 moves), leaves with zero or several coins.
pythondef distribute_coins(root): moves = 0 def excess(n): nonlocal moves if not n: return 0 l, r = excess(n.left), excess(n.right) moves += abs(l) + abs(r) return n.val - 1 + l + r excess(root) return movesjavaint moves; int distributeCoins(TreeNode root) { moves = 0; excess(root); return moves; } private int excess(TreeNode n) { if (n == null) return 0; int l = excess(n.left), r = excess(n.right); moves += Math.abs(l) + Math.abs(r); return n.val - 1 + l + r; }4 Unique binary search trees with n nodes
mediumChoose the root i from 1 to n. Then the left subtree uses i - 1 values and the right uses n - i, and the two are independent, so count = dp[i-1] * dp[n-i], summed over i. These are the Catalan numbers. Time O(n^2), space O(n). Edge cases: n equal to 0 or 1 (1), overflow beyond n around 19 for int (use long), counting shapes only not labels.
pythondef num_trees(n): dp = [1, 1] + [0] * max(0, n - 1) for k in range(2, n + 1): dp[k] = sum(dp[i - 1] * dp[k - i] for i in range(1, k + 1)) return dp[n]javalong numTrees(int n) { long[] dp = new long[Math.max(2, n + 1)]; dp[0] = dp[1] = 1; for (int k = 2; k <= n; k++) for (int i = 1; i <= k; i++) dp[k] += dp[i - 1] * dp[k - i]; return dp[n]; }5 Diameter of an n-ary tree given by edges
mediumA tree with a general number of children. A DFS returns the height of each subtree. At every node, the longest path through it joins the two tallest child arms, so keep the best two heights among its children. Track the maximum over all nodes. Pass the parent instead of a visited set. Time O(n), space O(h). Edge cases: a single node (0), a star where the root has the two longest arms, a path graph with the root in the middle or at an end, deep trees needing an iterative version.
pythondef tree_diameter(n, edges): g = [[] for _ in range(n)] for a, b in edges: g[a].append(b); g[b].append(a) best = 0 def height(u, parent): nonlocal best top1 = top2 = 0 for v in g[u]: if v == parent: continue h = height(v, u) + 1 if h > top1: top1, top2 = h, top1 elif h > top2: top2 = h best = max(best, top1 + top2) return top1 height(0, -1) return bestjavaint best; int treeDiameter(int n, int[][] edges) { List<List<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; i++) g.add(new ArrayList<>()); for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); } best = 0; height(g, 0, -1); return best; } private int height(List<List<Integer>> g, int u, int parent) { int top1 = 0, top2 = 0; for (int v : g.get(u)) { if (v == parent) continue; int h = height(g, v, u) + 1; if (h > top1) { top2 = top1; top1 = h; } else if (h > top2) top2 = h; } best = Math.max(best, top1 + top2); return top1; }6 Maximum weight independent set in a tree
mediumChoose vertices with no two adjacent to maximise total weight. For each vertex keep two values: the best in its subtree if it is taken (its weight plus the not-taken values of its children) and if it is not taken (the better of both for each child). The answer is the larger of the two at the root. House robber III is the binary special case. Time O(n), space O(h). Edge cases: a single vertex (its weight), negative weights (taking is never forced), a star where leaves beat the hub, recursion depth on a path graph.
pythondef max_independent_set(n, edges, w): g = [[] for _ in range(n)] for a, b in edges: g[a].append(b); g[b].append(a) def go(u, parent): take, skip = w[u], 0 for v in g[u]: if v == parent: continue t, s = go(v, u) take += s skip += max(t, s) return take, skip return max(go(0, -1))javaint maxIndependentSet(int n, int[][] edges, int[] w) { List<List<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; i++) g.add(new ArrayList<>()); for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); } int[] r = go(g, w, 0, -1); return Math.max(r[0], r[1]); } private int[] go(List<List<Integer>> g, int[] w, int u, int parent) { int take = w[u], skip = 0; for (int v : g.get(u)) { if (v == parent) continue; int[] r = go(g, w, v, u); take += r[1]; skip += Math.max(r[0], r[1]); } return new int[]{take, skip}; }7 Binary tree cameras: minimum cameras to monitor every node
hardA camera covers its node, parent and children. Use three states per node: 0 means not covered, 1 means has a camera, 2 means covered without a camera. A missing child counts as covered. If any child is uncovered, this node needs a camera (state 1). If any child has a camera, this node is covered (state 2). Otherwise it is uncovered (state 0) and its parent should place a camera. If the root ends uncovered, add one more. Time O(n), space O(h). Edge cases: a single node (1 camera), a leaf must never get a camera if its parent can, the root left uncovered, chains where every third node gets a camera.
pythondef min_camera_cover(root): cams = 0 def state(n): nonlocal cams if not n: return 2 l, r = state(n.left), state(n.right) if l == 0 or r == 0: cams += 1 return 1 if l == 1 or r == 1: return 2 return 0 if state(root) == 0: cams += 1 return camsjavaint cams; int minCameraCover(TreeNode root) { cams = 0; if (state(root) == 0) cams++; return cams; } private int state(TreeNode n) { // 0 uncovered, 1 camera, 2 covered if (n == null) return 2; int l = state(n.left), r = state(n.right); if (l == 0 || r == 0) { cams++; return 1; } if (l == 1 || r == 1) return 2; return 0; }8 Longest path in a tree with different adjacent characters
hardEach node has a character, and a path may only step between nodes with different characters. A tree is given by a parent array. For each node, take the longest downward paths into children whose characters differ, keep the top two, and the best path through the node is 1 plus those two. Return 1 plus the top one to the parent. Time O(n), space O(n). Edge cases: all characters equal (1), a single node, the best path passing through a node with several valid children, parent array with the root marked -1.
pythonimport sys def longest_path(parent, s): sys.setrecursionlimit(10**6) n = len(parent) children = [[] for _ in range(n)] for i in range(1, n): children[parent[i]].append(i) best = 1 def go(u): nonlocal best top1 = top2 = 0 for v in children[u]: h = go(v) if s[v] != s[u]: if h > top1: top1, top2 = h, top1 elif h > top2: top2 = h best = max(best, 1 + top1 + top2) return 1 + top1 go(0) return bestjavaint best; int longestPath(int[] parent, String s) { int n = parent.length; List<List<Integer>> children = new ArrayList<>(); for (int i = 0; i < n; i++) children.add(new ArrayList<>()); for (int i = 1; i < n; i++) children.get(parent[i]).add(i); best = 1; go(children, s, 0); return best; } private int go(List<List<Integer>> ch, String s, int u) { int top1 = 0, top2 = 0; for (int v : ch.get(u)) { int h = go(ch, s, v); if (s.charAt(v) != s.charAt(u)) { if (h > top1) { top2 = top1; top1 = h; } else if (h > top2) top2 = h; } } best = Math.max(best, 1 + top1 + top2); return 1 + top1; }9 Sum of distances from every node to all others (rerooting)
hardComputing a BFS from each node is O(n^2). Instead root the tree at 0, compute subtree sizes and the total distance from the root. Moving the root from a parent p to its child c brings the c-subtree one step closer and everyone else one step further: ans[c] = ans[p] - size[c] + (n - size[c]). Process nodes in DFS order so the parent is ready first. Time O(n), space O(n). Edge cases: a single node (0), a path graph, a star, an iterative traversal to avoid deep recursion on long paths.
pythondef sum_of_distances(n, edges): g = [[] for _ in range(n)] for a, b in edges: g[a].append(b); g[b].append(a) parent, order, seen = [-1] * n, [], [False] * n stack = [0] seen[0] = True while stack: u = stack.pop() order.append(u) for v in g[u]: if not seen[v]: seen[v] = True parent[v] = u stack.append(v) size = [1] * n down = [0] * n # distances inside the subtree for u in reversed(order): p = parent[u] if p >= 0: size[p] += size[u] down[p] += down[u] + size[u] ans = [0] * n ans[0] = down[0] for u in order[1:]: ans[u] = ans[parent[u]] - size[u] + (n - size[u]) return ansjavaint[] sumOfDistances(int n, int[][] edges) { List<List<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; i++) g.add(new ArrayList<>()); for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); } int[] parent = new int[n], order = new int[n], size = new int[n], ans = new int[n]; long[] down = new long[n]; Arrays.fill(parent, -1); boolean[] seen = new boolean[n]; Deque<Integer> st = new ArrayDeque<>(); st.push(0); seen[0] = true; int k = 0; while (!st.isEmpty()) { int u = st.pop(); order[k++] = u; for (int v : g.get(u)) if (!seen[v]) { seen[v] = true; parent[v] = u; st.push(v); } } Arrays.fill(size, 1); for (int i = n - 1; i >= 0; i--) { int u = order[i], p = parent[u]; if (p >= 0) { size[p] += size[u]; down[p] += down[u] + size[u]; } } ans[0] = (int) down[0]; for (int i = 1; i < n; i++) { int u = order[i]; ans[u] = ans[parent[u]] - size[u] + (n - size[u]); } return ans; }10 Largest BST subtree sum inside a binary tree
hardEach subtree reports four facts: whether it is a BST, its minimum, its maximum and its sum. A node forms a BST if both children are BSTs, left max is below the node value and right min is above it. When it does, update the global best with its sum. Empty subtrees report as BSTs with min set to infinity and max to negative infinity so they never block the checks. Time O(n), space O(h). Edge cases: all negative values (the best sum can be 0 for an empty BST), a tree with no valid BST larger than a leaf, a BST rooted in the middle of the tree.
pythondef max_sum_bst(root): best = 0 INF = float('inf') def go(n): nonlocal best if not n: return True, INF, -INF, 0 lb, lmin, lmax, ls = go(n.left) rb, rmin, rmax, rs = go(n.right) if lb and rb and lmax < n.val < rmin: total = ls + rs + n.val best = max(best, total) return True, min(lmin, n.val), max(rmax, n.val), total return False, 0, 0, 0 go(root) return bestjavaint best; int maxSumBST(TreeNode root) { best = 0; go(root); return best; } private long[] go(TreeNode n) { // {isBST, min, max, sum} if (n == null) return new long[]{1, Long.MAX_VALUE, Long.MIN_VALUE, 0}; long[] l = go(n.left), r = go(n.right); if (l[0] == 1 && r[0] == 1 && l[2] < n.val && n.val < r[1]) { long total = l[3] + r[3] + n.val; best = (int) Math.max(best, total); return new long[]{1, Math.min(l[1], n.val), Math.max(r[2], n.val), total}; } return new long[]{0, 0, 0, 0}; }
Frequently asked questions
What is tree DP?
It is dynamic programming over a tree, where each node computes a summary from its children, usually in post-order. It runs in O(n) because each node is processed once.
What is rerooting?
Rerooting computes an answer for every node as root. First compute subtree values with one root, then reuse them in a second pass that moves the root across each edge, adjusting the answer in O(1) per move.
How do I avoid recursion limits on deep trees?
Do an iterative traversal that records visiting order, then process nodes in reverse order so children are handled before parents. This is shown in the sum of distances solution.
Are tree DP questions common in interviews?
House robber III and binary tree cameras are well-known examples at product companies. The technical interview guide describes what rounds usually look like.
Related guides
More in DSA Interview Questions
- Tree Traversal Interview Questions
- Trie (Prefix Tree) Interview Questions
- Two pointers interview questions with worked solutions
- Union-Find (Disjoint Set Union) Interview Questions
- Array interview questions with worked solutions
- Backtracking interview questions with worked solutions
- BFS (Breadth-First Search) Interview Questions
- Binary search interview questions with worked solutions
- Binary Search Tree Interview Questions and Answers
- Binary Tree Interview Questions and Answers
- Bit manipulation interview questions with worked solutions
- Bitmask DP Interview Questions