Autocoder

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.

PatternPost-order traversal returning a summary
Typical costO(n) time, O(h) space
Common summariesPairs, three states, tuples
AdvancedRerooting 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

Tree DP Interview Questions: questions with worked answers

  1. 1

    House robber III: loot a binary tree of houses

    medium

    Robbing 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.

    python
    def 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))
    java
    int 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. 2

    Longest path of equal values in a binary tree

    medium

    Each 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.

    python
    def 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 best
    java
    int 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. 3

    Distribute coins in a binary tree so every node has one

    medium

    Return 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.

    python
    def 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 moves
    java
    int 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. 4

    Unique binary search trees with n nodes

    medium

    Choose 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.

    python
    def 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]
    java
    long 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. 5

    Diameter of an n-ary tree given by edges

    medium

    A 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.

    python
    def 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 best
    java
    int 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. 6

    Maximum weight independent set in a tree

    medium

    Choose 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.

    python
    def 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))
    java
    int 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. 7

    Binary tree cameras: minimum cameras to monitor every node

    hard

    A 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.

    python
    def 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 cams
    java
    int 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. 8

    Longest path in a tree with different adjacent characters

    hard

    Each 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.

    python
    import 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 best
    java
    int 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. 9

    Sum of distances from every node to all others (rerooting)

    hard

    Computing 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.

    python
    def 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 ans
    java
    int[] 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. 10

    Largest BST subtree sum inside a binary tree

    hard

    Each 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.

    python
    def 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 best
    java
    int 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

See all in this section