Maximum Sum of nodes in Binary tree such that no two are adjacent

The problem, simply

Every node of a binary tree holds a number. Choose some nodes so that their total is as big as possible. The rule: you may never choose two nodes that are joined by a line, so never a parent together with its own child. Give back the biggest total.

This is the famous "house robber" puzzle on a tree: houses joined by a line share an alarm, so you cannot rob both.

A story to remember it

Picture it

Examples

Way 1: the simple way

At each node, try both choices with plain recursion.

• Take the node: add its value, skip its children, and solve each grandchild.
• Skip the node: solve each child.

Return the bigger one.

class Solution {
    public int maxSum(TreeNode node) {
        if (node == null) return 0;
        int take = node.val;                           // take me, skip my children
        if (node.left != null) take += maxSum(node.left.left) + maxSum(node.left.right);
        if (node.right != null) take += maxSum(node.right.left) + maxSum(node.right.right);
        int skip = maxSum(node.left) + maxSum(node.right);   // skip me
        return Math.max(take, skip);
    }
}

How long it takes: the same subtree is solved again from many places. On a long thin tree the number of calls grows like the Fibonacci numbers, which is exponential, so think of it as O(2^n). Extra room: the call stack, O(h). You can save it with a memo map from node to answer, which makes it O(n) time and O(n) room.

Way 2: the clever way

Make every node return two numbers at once, like the party notes:

• take: the best total of my family if I am picked. Then my children are not picked, so take = my value + left.skip + right.skip.
• skip: the best total if I am not picked. Each child may do what is best for it, so skip = max(left.take, left.skip) + max(right.take, right.skip).

An empty spot returns (0, 0). The answer is the bigger of the root's two numbers. Every node is solved exactly once, children before parents.

class Solution {
    public int maxSum(TreeNode root) {
        int[] best = solve(root);
        return Math.max(best[0], best[1]);
    }

    // returns {take, skip} for this family
    private int[] solve(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] left = solve(node.left);
        int[] right = solve(node.right);
        int take = node.val + left[1] + right[1];                         // children must stay home
        int skip = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // children choose freely
        return new int[]{take, skip};
    }
}

How long it takes: one visit per node, O(n). Extra room: the call stack, O(h). No memo map is needed, because each node passes both numbers up in one go.

Watch out for

• In skip, do not force the children to be taken. Use max(take, skip) for each child, because sometimes skipping two floors in a row is best.
• If values can be negative, the code still works: skip lets you pick nothing in a family, which is worth 0.
• The empty tree returns 0.

What interviewers ask next

• House robber on a line of houses: the same two numbers, carried from left to right instead of from leaves to root.
• Also return which nodes were picked. Walk down again: at the root take the bigger choice; if a node is taken, its children are skipped; if skipped, each child picks its own bigger choice.
• Largest set of nodes with no two joined, ignoring values (maximum independent set on a tree): the same code with every value equal to 1.
• Smallest set of nodes that touches every line (minimum vertex cover on a tree): also two or three numbers per node, combined from children.

Remember this

Grown-up words: the two numbers per node are the dynamic programming states, solving children before the parent is a postorder depth first search, "no two joined" is an independent set, and this is LeetCode's "house robber III".