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:
       9
     /   \
    /     \
   5       11
  /  \     /
 3    7   10
 \   
  4 

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 (
            sizeIncludingCurr+1, 
            sizeExcludingCurr
       );
}


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:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal