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.
|
