Largest Independent Set Problem

The problem, simply

You get a binary tree. Choose as many nodes as you can, with one rule: no chosen node may be the parent or child of another chosen node. Grandparent and grandchild are fine, and so are brothers and sisters.

Give back how many nodes you can choose. A group where no two are joined by a branch is called an independent set, so this is the largest independent set of a tree.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each node, try both choices and keep the better one.

1. If the node is empty, the answer is 0.
2. Skip the node: answer for the left child plus answer for the right child.
3. Invite the node: 1, plus the answers for all four grandchildren (the children must stay home).
4. Return the bigger of the two.

class Solution {
    public int lisBrute(TreeNode root) {
        if (root == null) return 0;

        int skip = lisBrute(root.left) + lisBrute(root.right);   // ask the children

        int invite = 1;                                           // ask the grandchildren
        if (root.left != null) invite += lisBrute(root.left.left) + lisBrute(root.left.right);
        if (root.right != null) invite += lisBrute(root.right.left) + lisBrute(root.right.right);

        return Math.max(skip, invite);
    }
}

How long it takes: each node is solved once by its parent and again by its grandparent, and those repeats multiply as you go down. On a long thin tree the count grows like the Fibonacci numbers, which is exponential, O(2^n) as an upper bound. Extra room: the call chain is as deep as the tree, O(h). Adding a memo map from node to answer brings it down to O(n).

Way 2: the clever way

Do one walk where children report before parents (post order), and let every node return two numbers.

1. An empty node returns in = 0, out = 0.
2. For a node, first get the reports from its left and right child.
3. in = 1 + left.out + right.out. I am invited, so my children stay home.
4. out = max(left.in, left.out) + max(right.in, right.out). I stay home, so each child does what is best for its own branch.
5. The answer is max(root.in, root.out).

class Solution {
    // returns {in, out}: best size if this node is invited, and if it is not
    private int[] solve(TreeNode node) {
        if (node == null) return new int[] {0, 0};
        int[] l = solve(node.left);               // children report first
        int[] r = solve(node.right);
        int in = 1 + l[1] + r[1];                 // invited: children stay home
        int out = Math.max(l[0], l[1]) + Math.max(r[0], r[1]); // skipped: children choose
        return new int[] {in, out};
    }

    public int largestIndependentSet(TreeNode root) {
        int[] res = solve(root);
        return Math.max(res[0], res[1]);
    }
}

How long it takes: every node is visited once and does a few additions, O(n). Extra room: the call chain is as deep as the tree, O(h), which is O(n) for a tree shaped like a line and O(log n) for a balanced one.

Watch out for

• Grandparent and grandchild may both be invited. Only direct parent and child are forbidden.
• Empty tree: return 0. The null case returning {0, 0} handles this.
• A very deep tree can overflow the Java call stack. Use an explicit stack and a post order loop if the tree can be a long chain of 100,000 nodes.

What interviewers ask next

• Return the people, not just the count. Walk down from the root: if a node is allowed and in >= out, take it and mark its children "not allowed"; otherwise move on to its children with "allowed".
• House Robber III: same tree, but each node has money and you maximize the sum. Replace 1 + with node.val +.
• What about a general graph? Largest independent set is NP hard on general graphs. Trees are easy because cutting a node splits the problem into separate branches.
• Smallest vertex cover of a tree: it is n minus the largest independent set, or its own DP: in = 1 + sum of min(child in, child out), out = sum of child in.
• Nodes with many children (an n-ary tree): same two numbers, sum over all children.

Remember this

Grown-up words: the party group is an independent set, the family tree is a binary tree, children reporting before parents is a post order traversal, and the two numbers per node are the states of tree dynamic programming.