Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

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: