Make delicious recipes!

Largest independent subset in a tree

Problem: Given a binary tree, find the largest independent subset in the tree.
LISS is defined as the largest subset such that no two nodes in that set share an edge.
Example: In the following tree:
     /   \
    /     \
   5       11
  /  \     /
 3    7   10

Some big independent subsets are:
[9, 3, 7, 10]
[5, 11, 4]

The biggest one among them is [9,3,7,10]

Solution: Clearly, we need to consider grand children of a node and then consider their grand children.
Recursively, this can be written as:

int liss(TreeNode root)
    if (root == null)
       return 0;
    // Find size including the current node
    int sizeIncludingCurr = 0;
    if (root.left != null)
       sizeIncludingCurr += liss(root.left.left) + liss(root.left.right);
    if (root.right != null)
       sizeIncludingCurr += liss(root.right.left) + liss(root.right.right);
    // Now find size excluding the current node
    int sizeExcludingCurr = liss(root.left) + liss(root.right);
    // Return the maximum of two sizes
    return max (

The order of the above solution is exponential since it calculates the subproblems again and again.
This can be improved to O(n) by adding a map storing TreeNode as the key and the liss-count for it.

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Email: (Your email is not shared with anybody)

Facebook comments:

Site Owner: Sachin Goyal