Largest Independent Set Problem

Problem Statement

Given a binary tree, find the size of the Largest Independent Set (LIS). An independent set is a set of nodes in the tree such that no two nodes in the set are directly connected (i.e., no parent-child pair is in the set).

Example:

• Input: A binary tree:

• Output: 4 (The largest independent set is 10 — wait, 10 and 30 are connected. Correct set: 10 — 10 and 40 are connected via 20. Actually: 30 — but 30 and 60 are connected. Valid: 30 size 3, or 10... Correct LIS = 10 is invalid. Best: 60 has size 3, or 30 size 2, or 30 invalid (50→20→... 30 not connected to 50 directly). Valid: 60 = 3 or 60 = 2. Actually 60 = 3 since none are parent-child.)

Let's use a clearer example:

• Output: 4 for a well-structured tree

Noob-Friendly Explanation

Imagine a company org chart (a tree). You're planning a party and have one rule: if you invite a manager, you can't invite anyone who directly reports to them (and vice versa). You want to invite as many people as possible. Who do you invite to get the biggest guest list while following the rule?

Approach 1: Brute Force

Intuition

For each node, we have two choices: include it or exclude it. If we include a node, we cannot include its children. If we exclude it, we can include or exclude its children. Try both options and take the maximum.

Algorithm

1. If the node is null, return 0.
2. Exclude current node: LIS = LIS(left child) + LIS(right child).
3. Include current node: LIS = 1 + LIS(grandchildren).
4. Return the maximum of include and exclude.

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
        left = right = null;
    }
}

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

        // Option 1: Exclude root
        int exclude = lisBrute(root.left) + lisBrute(root.right);

        // Option 2: Include root — skip children, go to grandchildren
        int include = 1;
        if (root.left != null) {
            include += lisBrute(root.left.left) + lisBrute(root.left.right);
        }
        if (root.right != null) {
            include += lisBrute(root.right.left) + lisBrute(root.right.right);
        }

        return Math.max(include, exclude);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(20);
        root.right = new TreeNode(30);
        root.left.left = new TreeNode(40);
        root.left.right = new TreeNode(50);
        root.right.right = new TreeNode(60);

        System.out.println(lisBrute(root)); // Output: 4
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - exponential because of overlapping subproblems
• Space Complexity: O(n) - recursion stack depth (height of tree)

Approach 2: Optimal

Intuition

Use memoization (or a bottom-up approach). Store the LIS result for each node to avoid recomputation. Alternatively, return a pair from each node: (size including this node, size excluding this node).

Algorithm

1. For each node, compute two values: include (LIS including this node) and exclude (LIS excluding this node).
2. include = 1 + exclude(left) + exclude(right) — if we include current, we must exclude children.
3. exclude = max(include(left), exclude(left)) + max(include(right), exclude(right)).
4. Return the max of include and exclude for the root.

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
        left = right = null;
    }
}

class Solution {
    // Returns int[]{include, exclude}
    public static int[] lisOptimal(TreeNode root) {
        if (root == null) return new int[]{0, 0};

        int[] left = lisOptimal(root.left);
        int[] right = lisOptimal(root.right);

        // Include root: must exclude children
        int include = 1 + left[1] + right[1];

        // Exclude root: take the best of include/exclude for each child
        int exclude = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        return new int[]{include, exclude};
    }

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

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(20);
        root.right = new TreeNode(30);
        root.left.left = new TreeNode(40);
        root.left.right = new TreeNode(50);
        root.right.right = new TreeNode(60);

        System.out.println(largestIndependentSet(root)); // Output: 4
    }
}

Complexity Analysis

• Time Complexity: O(n) - each node is visited exactly once
• Space Complexity: O(n) - recursion stack depth (height of tree, O(n) worst case for skewed tree)