SyntaxPilot
Courses/DSA and Coding Problems/Lesson 76
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 76 of 90

DP on trees: house robber III

queued

These are the notes for DSA episode 76. An office is planning a Diwali party. The org chart is a tree, everyone has a fun score, and one rule: never invite a person together with their direct boss. Which guest list has the most fun? (LeetCode tells it as a thief and houses on a tree.) We try every other level (a wrong answer on screen: 6 instead of 7), then take or skip at every node, recomputed (correct, then Time Limit Exceeded on two million people), see that every node is solved again by its parent and its grandparent, and find the insight: let every node return two numbers, {take, skip}, in one postorder pass. Then two million nodes in under a tenth of a second and three real bugs. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).

The problem, in real life

The office party In code
The org chart a binary tree
A person's fun score node.val
"never with your direct boss" never pick a parent and its child
The guest list a set of chosen nodes
The most fun the maximum sum

Every word, from zero

  • Binary tree: nodes where each node has at most two children, left and right; the top node is the root, nodes with no children are leaves.
  • Parent / child / grandchild: a node's direct links down are its children; their children are its grandchildren.
  • Subtree: a node together with everything below it.
  • Independent set: a set of nodes with no two directly linked. This problem asks for the maximum-weight independent set of a tree.
  • Postorder: visit the children first, then the node itself. Needed when a node's answer depends on its children's answers.
  • Tree DP: dynamic programming where each node computes its answer from its children's answers.
  • State: what a node reports to its parent; here a pair {take, skip}.
  • take: the best sum in this subtree if this node is picked.
  • skip: the best sum in this subtree if this node is not picked.
  • Memoization: remembering answers already computed (here a HashMap<Node, Integer> would also work).
  • Height h: the number of levels from the root to the deepest leaf; it is the recursion depth.

Problem statement

House Robber III (LeetCode 337). The houses form a binary tree; two directly linked houses can't both be robbed. Return the maximum amount. Up to 10⁴ nodes, 0 ≤ val ≤ 10⁴.

Tree Answer Picked
a: 3 → (2 → right 3), (3 → right 1) 7 3 (root), 3, 1
b: 3 → (4 → 1, 3), (5 → right 1) 9 4, 5
c: 2 → (1 → right 4), 3 7 4, 3
empty 0
single 5 5 5

Obvious idea 1: every other level

Parents and children are on neighbouring levels, so take all even levels or all odd levels?

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int rob(Node root) {
        int even = 0, odd = 0, level = 0;
        Queue<Node> q = new ArrayDeque<>();
        if (root != null) q.add(root);
        while (!q.isEmpty()) {
            int sum = 0;
            for (int k = q.size(); k > 0; k--) {
                Node n = q.poll();
                sum += n.val;
                if (n.left != null) q.add(n.left);
                if (n.right != null) q.add(n.right);
            }
            if (level % 2 == 0) even += sum; else odd += sum;
            level++;
        }
        return Math.max(even, odd);
    }
    public static void main(String[] args) {
        Node a = new Node(3, new Node(2, null, new Node(3)),
                             new Node(3, null, new Node(1)));
        Node b = new Node(3, new Node(4, new Node(1), new Node(3)),
                             new Node(5, null, new Node(1)));
        Node c = new Node(2, new Node(1, null, new Node(4)), new Node(3));
        System.out.println(rob(a));
        System.out.println(rob(b));
        System.out.println(rob(c));
    }
}
7
9
6

6 instead of 7 for tree c: the best list (4 and 3) uses level 2 and level 1. Whole levels are too crude.

Obvious idea 2: take or skip at every node

Take a node: its value plus the best of its four grandchildren. Skip it: the best of its two children.

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int rob(Node n) {
        if (n == null) return 0;
        int take = n.val;
        if (n.left != null) take += rob(n.left.left) + rob(n.left.right);
        if (n.right != null) take += rob(n.right.left) + rob(n.right.right);
        int skip = rob(n.left) + rob(n.right);
        return Math.max(take, skip);
    }
    public static void main(String[] args) {
        Node a = new Node(3, new Node(2, null, new Node(3)),
                             new Node(3, null, new Node(1)));
        Node b = new Node(3, new Node(4, new Node(1), new Node(3)),
                             new Node(5, null, new Node(1)));
        Node c = new Node(2, new Node(1, null, new Node(4)), new Node(3));
        System.out.println(rob(a));
        System.out.println(rob(b));
        System.out.println(rob(c));
        System.out.println(rob(null));
        System.out.println(rob(new Node(5)));
    }
}
7
9
7
0
5

Correct. Now a full tree 21 levels deep, about two million people:

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int next = 0;
    static Node build(int depth) {
        if (depth == 0) return null;
        Node n = new Node(next++ % 10 + 1);
        n.left = build(depth - 1);
        n.right = build(depth - 1);
        return n;
    }
    static int rob(Node n) {
        if (n == null) return 0;
        int take = n.val;
        if (n.left != null) take += rob(n.left.left) + rob(n.left.right);
        if (n.right != null) take += rob(n.right.left) + rob(n.right.right);
        int skip = rob(n.left) + rob(n.right);
        return Math.max(take, skip);
    }
    public static void main(String[] args) {
        Node big = build(21);
        long t0 = System.nanoTime();
        int r = rob(big);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(next + " people: " + r + ", " + ms + " ms");
    }
}

(no output: still running after 25 s: Time Limit Exceeded)

Why is it slow?

  • rob(x) is called by x's parent (when the parent is skipped) and by x's grandparent (when the grandparent is taken).
  • Those callers are called twice too, so the calls grow like the Fibonacci numbers, level after level.
  • Fix 1: memoize in a HashMap<Node, Integer>: O(n). Fix 2, cleaner: return both answers from each node, so each node is solved once.

The key insight: return {take, skip}

solve(null)  = {0, 0}
take(n)      = n.val + skip(left) + skip(right)            children must be skipped
skip(n)      = max(take(left), skip(left)) + max(take(right), skip(right))   children are free
answer       = max(take(root), skip(root))

By hand: tree b

Node take skip Pair
leaf 1 (under 4) 1 0 (1, 0)
leaf 3 3 0 (3, 0)
leaf 1 (under 5) 1 0 (1, 0)
4 4 + 0 + 0 = 4 1 + 3 = 4 (4, 4)
5 5 + 0 = 5 1 (5, 1)
root 3 3 + 4 + 1 = 8 4 + 5 = 9 (8, 9)

Solution in Java

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int[] solve(Node n) {
        if (n == null) return new int[]{0, 0};
        int[] L = solve(n.left);
        int[] R = solve(n.right);
        int take = n.val + L[1] + R[1];
        int skip = Math.max(L[0], L[1]) + Math.max(R[0], R[1]);
        return new int[]{take, skip};
    }
    static int rob(Node root) {
        int[] r = solve(root);
        return Math.max(r[0], r[1]);
    }
    public static void main(String[] args) {
        Node a = new Node(3, new Node(2, null, new Node(3)),
                             new Node(3, null, new Node(1)));
        Node b = new Node(3, new Node(4, new Node(1), new Node(3)),
                             new Node(5, null, new Node(1)));
        Node c = new Node(2, new Node(1, null, new Node(4)), new Node(3));
        System.out.println(rob(a));
        System.out.println(rob(b));
        System.out.println(rob(c));
        System.out.println(rob(null));
        System.out.println(rob(new Node(5)));
    }
}
7
9
7
0
5

The two million people that timed out:

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int next = 0;
    static Node build(int depth) {
        if (depth == 0) return null;
        Node n = new Node(next++ % 10 + 1);
        n.left = build(depth - 1);
        n.right = build(depth - 1);
        return n;
    }
    static int[] solve(Node n) {
        if (n == null) return new int[]{0, 0};
        int[] L = solve(n.left);
        int[] R = solve(n.right);
        int take = n.val + L[1] + R[1];
        int skip = Math.max(L[0], L[1]) + Math.max(R[0], R[1]);
        return new int[]{take, skip};
    }
    static int rob(Node root) {
        int[] r = solve(root);
        return Math.max(r[0], r[1]);
    }
    public static void main(String[] args) {
        Node big = build(21);
        long t0 = System.nanoTime();
        int r = rob(big);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(next + " people: " + r + ", " + ms + " ms");
    }
}
2097151 people: 7749744, 70 ms

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};

// House robber III: solve(n) returns {take, skip} for n's subtree, in one postorder pass.
pair<int, int> solve(Node* n) {
    if (!n) return {0, 0};
    auto [lt, ls] = solve(n->left);
    auto [rt, rs] = solve(n->right);
    int take = n->val + ls + rs;                     // children must be skipped
    int skip = max(lt, ls) + max(rt, rs);            // children are free
    return {take, skip};
}

int rob(Node* root) {
    auto [t, s] = solve(root);
    return max(t, s);
}

int main() {
    Node* a = new Node(3, new Node(2, nullptr, new Node(3)), new Node(3, nullptr, new Node(1)));
    Node* b = new Node(3, new Node(4, new Node(1), new Node(3)), new Node(5, nullptr, new Node(1)));
    Node* c = new Node(2, new Node(1, nullptr, new Node(4)), new Node(3));
    cout << rob(a) << "\n" << rob(b) << "\n" << rob(c) << "\n";
    cout << rob(nullptr) << "\n" << rob(new Node(5)) << "\n";
}
7
9
7
0
5

The same solution in Python

# House robber III: solve(n) returns (take, skip) for n's subtree, in one postorder pass.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def solve(n):
    if n is None:
        return 0, 0
    lt, ls = solve(n.left)
    rt, rs = solve(n.right)
    take = n.val + ls + rs              # children must be skipped
    skip = max(lt, ls) + max(rt, rs)    # children are free
    return take, skip

def rob(root):
    return max(solve(root))

a = Node(3, Node(2, None, Node(3)), Node(3, None, Node(1)))
b = Node(3, Node(4, Node(1), Node(3)), Node(5, None, Node(1)))
c = Node(2, Node(1, None, Node(4)), Node(3))
for t in (a, b, c, None, Node(5)):
    print(rob(t))
7
9
7
0
5

(For a very deep tree, raise Python's recursion limit with sys.setrecursionlimit, or use an iterative postorder.)

Three real bugs

Bug 1: skipping a node forces both children to be taken. On the chain 4 → 1 → 1 → 4 the best is 8 (the two 4s), which skips two nodes in a row.

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int[] solve(Node n) {
        if (n == null) return new int[]{0, 0};
        int[] L = solve(n.left);
        int[] R = solve(n.right);
        int take = n.val + L[1] + R[1];
        int skip = L[0] + R[0];
        return new int[]{take, skip};
    }
    static int rob(Node root) {
        int[] r = solve(root);
        return Math.max(r[0], r[1]);
    }
    public static void main(String[] args) {
        Node d = new Node(4, new Node(1, new Node(1, new Node(4), null), null), null);
        System.out.println(rob(d));
    }
}
5

Bug 2: taking a node adds the children's take. That invites a parent and its child together: the answer is bigger than the true best.

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int[] solve(Node n) {
        if (n == null) return new int[]{0, 0};
        int[] L = solve(n.left);
        int[] R = solve(n.right);
        int take = n.val + L[0] + R[0];
        int skip = Math.max(L[0], L[1]) + Math.max(R[0], R[1]);
        return new int[]{take, skip};
    }
    static int rob(Node root) {
        int[] r = solve(root);
        return Math.max(r[0], r[1]);
    }
    public static void main(String[] args) {
        Node a = new Node(3, new Node(2, null, new Node(3)),
                             new Node(3, null, new Node(1)));
        Node b = new Node(3, new Node(4, new Node(1), new Node(3)),
                             new Node(5, null, new Node(1)));
        Node c = new Node(2, new Node(1, null, new Node(4)), new Node(3));
        System.out.println(rob(a));
        System.out.println(rob(b));
    }
}
12
17

Bug 3: a leaf as the base case instead of null. Node 2 in tree a has only a right child, so solve is called on its missing left child.

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int[] solve(Node n) {
        if (n.left == null && n.right == null) return new int[]{n.val, 0};
        int[] L = solve(n.left);
        int[] R = solve(n.right);
        int take = n.val + L[1] + R[1];
        int skip = Math.max(L[0], L[1]) + Math.max(R[0], R[1]);
        return new int[]{take, skip};
    }
    static int rob(Node root) {
        int[] r = solve(root);
        return Math.max(r[0], r[1]);
    }
    public static void main(String[] args) {
        Node a = new Node(3, new Node(2, null, new Node(3)),
                             new Node(3, null, new Node(1)));
        Node b = new Node(3, new Node(4, new Node(1), new Node(3)),
                             new Node(5, null, new Node(1)));
        Node c = new Node(2, new Node(1, null, new Node(4)), new Node(3));
        System.out.println(rob(a));
    }
}
Exception in thread "main" java.lang.NullPointerException: Cannot read field "left" because "<parameter1>" is null
    at Main.solve(Main.java:11)
    at Main.solve(Main.java:12)
    at Main.solve(Main.java:12)
    at Main.rob(Main.java:19)
    at Main.main(Main.java:28)

(The message says <parameter1> because the class was compiled without debug names; compiled with javac -g it says because "n" is null.)

Complexity

Approach Time Space Big input
Every other level O(n) O(width) fast but wrong
Take or skip, recomputed exponential in the height O(h) stack 2 million nodes: Time Limit Exceeded
Memo in a HashMap O(n) O(n) works
Two answers per node O(n) O(h) stack 2 million nodes: ~90 ms

Common mistakes

Mistake What you see (real) Why Fix
Every other level 6 instead of 7 the best list mixes levels decide per node
skip = L.take + R.take 5 instead of 8 a skipped node's children may be skipped too max(take, skip) per child
take = val + L.take + R.take 12 and 17 (too big) parent and child both picked val + L.skip + R.skip
Leaf as the base case NullPointerException: Cannot read field "left" because "<parameter1>" is null one-child nodes call solve(null) if (n == null) return {0, 0}
Returning only one number exponential time again the parent needs both answers return the pair
Greedy "take if bigger than children" wrong on deeper trees decisions interact two levels down the DP pair

Mini project: the party planner

Build the org chart of a small company from a list of (employee, boss, fun) rows (a general tree, not binary: loop over all children), compute the best total, and print the guest list. Then add a rule: the CEO must be invited.

Practice

1. Binary Tree Cameras (LeetCode 968). Place the fewest cameras so every node is watched (a camera watches its parent, itself and its children). Three states: not covered, has a camera, covered.

2. House Robber II (LeetCode 213). Houses in a circle: run the line version twice, without the first house and without the last.

3. Maximum sum of non-adjacent nodes in a general tree. The same pair, summed over all children.

4. Return the guest list, not just the sum.

Solutions (1 and 4)
import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    // Binary Tree Cameras (LeetCode 968): three states per node.
    // 0 = not covered yet, 1 = has a camera, 2 = covered (by a child's camera). null counts as covered.
    static int cameras;
    static int state(Node n) {
        if (n == null) return 2;
        int l = state(n.left), r = state(n.right);
        if (l == 0 || r == 0) { cameras++; return 1; }   // a child needs me
        if (l == 1 || r == 1) return 2;                  // a child's camera covers me
        return 0;                                        // ask my parent
    }
    static int minCameras(Node root) {
        cameras = 0;
        if (state(root) == 0) cameras++;
        return cameras;
    }
    // Homework 4: return the guest list, not just the sum.
    static Map<Node, int[]> memo = new HashMap<>();
    static int[] solve(Node n) {
        if (n == null) return new int[]{0, 0};
        int[] L = solve(n.left), R = solve(n.right);
        int[] res = {n.val + L[1] + R[1], Math.max(L[0], L[1]) + Math.max(R[0], R[1])};
        memo.put(n, res);
        return res;
    }
    static void pick(Node n, boolean mayTake, List<Integer> out) {
        if (n == null) return;
        int[] s = memo.get(n);
        boolean take = mayTake && s[0] >= s[1];
        if (take) out.add(n.val);
        pick(n.left, !take, out);
        pick(n.right, !take, out);
    }
    public static void main(String[] args) {
        Node t1 = new Node(0, new Node(0, new Node(0), new Node(0)), null);
        Node t2 = new Node(0, new Node(0, new Node(0, new Node(0, null, new Node(0)), null), null), null);
        System.out.println(minCameras(t1));
        System.out.println(minCameras(t2));
        Node b = new Node(3, new Node(4, new Node(1), new Node(3)), new Node(5, null, new Node(1)));
        int[] r = solve(b);
        List<Integer> guests = new ArrayList<>();
        pick(b, true, guests);
        System.out.println(Math.max(r[0], r[1]) + " " + guests);
    }
}
1
2
9 [4, 5]

Quick quiz

A 5 at the top with one child 1, and the 1 has two children, both 4. The best total? A) 5 B) 8 C) 9 D) 13

Answer

D) 13. Take 5 and both 4s: the 4s are children of 1, not of 5. Skipping 5 gives only 4 + 4 = 8.

Interview questions

  1. Why does taking every other level fail? The best set can mix levels when a node is skipped two levels in a row.
  2. Why is the plain recursion slow? Each node is recomputed by its parent and grandparent; the calls grow like Fibonacci.
  3. What does each node return, and why two numbers? {take, skip}: the parent needs the child's best with the child picked and without it.
  4. Recurrence? take = val + L.skip + R.skip, skip = max(L) + max(R).
  5. Traversal order? Postorder: children first.
  6. Complexity? O(n) time, O(h) recursion stack.
  7. How does this extend to general trees? Sum over all children: take = val + Σ skip(child), skip = Σ max(child).

Glossary

Term Meaning
Binary tree Nodes with at most two children
Root / leaf The top node / a node with no children
Subtree A node and everything below it
Independent set Nodes with no two directly linked
Postorder Children first, then the node
Tree DP Each node's answer built from its children's answers
take Best sum of the subtree with this node picked
skip Best sum of the subtree without this node
Memoization Remembering computed answers
Height Levels from root to the deepest leaf: the recursion depth
Fibonacci growth Each count is the sum of the two before: exponential

Summary

  • Whole levels give wrong answers; take-or-skip recomputed is right but exponential.
  • Every node returns {take, skip}: take = val + L.skip + R.skip, skip = max(L) + max(R); answer max at the root.
  • null is the base case; one postorder pass, O(n) time, O(h) space.
  • Next episode: bitmask DP and the travelling salesman problem, a set of cities stored in the bits of an int.