Given a Binary Tree, find size of the Largest Independent Set(LIS) in it. A subset of all tree nodes is an independent set if there is no edge between any two nodes of the subset.
For example, consider the following binary tree. The largest independent set(LIS) is {10, 40, 60, 70, 80} and size of the LIS is 5.
A Dynamic Programming solution solves a given problem using solutions of subproblems in bottom up manner. Can the given problem be solved using solutions to subproblems? If yes, then what are the subproblems? Can we find largest independent set size (LISS) for a node X if we know LISS for all descendants of X? If a node is considered as part of LIS, then its children cannot be part of LIS, but its grandchildren can be. Following is optimal substructure property.
[ad type=”banner”]- Optimal Substructure:
Let LISS(X) indicates size of largest independent set of a tree with root X.
LISS(X) = MAX { (1 + sum of LISS for all grandchildren of X),
(sum of LISS for all children of X) }
The idea is simple, there are two possibilities for every node X, either X is a member of the set or not a member. If X is a member, then the value of LISS(X) is 1 plus LISS of all grandchildren. If X is not a member, then the value is sum of LISS of all children.
- Overlapping Subproblems
Following is recursive implementation that simply follows the recursive structure mentioned above.
[pastacode lang=”c” manual=”%2F%2F%20A%20naive%20recursive%20implementation%20of%20Largest%20Independent%20Set%20problem%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%20%0A%2F%2F%20A%20utility%20function%20to%20find%20max%20of%20two%20integers%0Aint%20max(int%20x%2C%20int%20y)%20%7B%20return%20(x%20%3E%20y)%3F%20x%3A%20y%3B%20%7D%0A%20%0A%2F*%20A%20binary%20tree%20node%20has%20data%2C%20pointer%20to%20left%20child%20and%20a%20pointer%20to%20%0A%20%20%20right%20child%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node%20*left%2C%20*right%3B%0A%7D%3B%0A%20%0A%2F%2F%20The%20function%20returns%20size%20of%20the%20largest%20independent%20set%20in%20a%20given%20%0A%2F%2F%20binary%20tree%0Aint%20LISS(struct%20node%20*root)%0A%7B%0A%20%20%20%20if%20(root%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20return%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Caculate%20size%20excluding%20the%20current%20node%0A%20%20%20%20int%20size_excl%20%3D%20LISS(root-%3Eleft)%20%2B%20LISS(root-%3Eright)%3B%0A%20%0A%20%20%20%20%2F%2F%20Calculate%20size%20including%20the%20current%20node%0A%20%20%20%20int%20size_incl%20%3D%201%3B%0A%20%20%20%20if%20(root-%3Eleft)%0A%20%20%20%20%20%20%20size_incl%20%2B%3D%20LISS(root-%3Eleft-%3Eleft)%20%2B%20LISS(root-%3Eleft-%3Eright)%3B%0A%20%20%20%20if%20(root-%3Eright)%0A%20%20%20%20%20%20%20size_incl%20%2B%3D%20LISS(root-%3Eright-%3Eleft)%20%2B%20LISS(root-%3Eright-%3Eright)%3B%0A%20%0A%20%20%20%20%2F%2F%20Return%20the%20maximum%20of%20two%20sizes%0A%20%20%20%20return%20max(size_incl%2C%20size_excl)%3B%0A%7D%0A%20%0A%20%0A%2F%2F%20A%20utility%20function%20to%20create%20a%20node%0Astruct%20node*%20newNode(%20int%20data%20)%0A%7B%0A%20%20%20%20struct%20node*%20temp%20%3D%20(struct%20node%20*)%20malloc(%20sizeof(struct%20node)%20)%3B%0A%20%20%20%20temp-%3Edata%20%3D%20data%3B%0A%20%20%20%20temp-%3Eleft%20%3D%20temp-%3Eright%20%3D%20NULL%3B%0A%20%20%20%20return%20temp%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Let%20us%20construct%20the%20tree%20given%20in%20the%20above%20diagram%0A%20%20%20%20struct%20node%20*root%20%20%20%20%20%20%20%20%20%3D%20newNode(20)%3B%0A%20%20%20%20root-%3Eleft%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3D%20newNode(8)%3B%0A%20%20%20%20root-%3Eleft-%3Eleft%20%20%20%20%20%20%20%20%20%20%3D%20newNode(4)%3B%0A%20%20%20%20root-%3Eleft-%3Eright%20%20%20%20%20%20%20%20%20%3D%20newNode(12)%3B%0A%20%20%20%20root-%3Eleft-%3Eright-%3Eleft%20%20%20%3D%20newNode(10)%3B%0A%20%20%20%20root-%3Eleft-%3Eright-%3Eright%20%20%3D%20newNode(14)%3B%0A%20%20%20%20root-%3Eright%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3D%20newNode(22)%3B%0A%20%20%20%20root-%3Eright-%3Eright%20%20%20%20%20%20%20%20%3D%20newNode(25)%3B%0A%20%0A%20%20%20%20printf%20(%22Size%20of%20the%20Largest%20Independent%20Set%20is%20%25d%20%22%2C%20LISS(root))%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”C” highlight=”” provider=”manual”/]Output :
Size of the Largest Independent Set is 5[ad type=”banner”]
Time complexity of the above naive recursive approach is exponential. It should be noted that the above function computes the same subproblems again and again. For example, LISS of node with value 50 is evaluated for node with values 10 and 20 as 50 is grandchild of 10 and child of 20.
Since same suproblems are called again, this problem has Overlapping Subprolems property. So LISS problem has both properties of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by storing the solutions to subproblems and solving problems in bottom up manner.
Following is C implementation of Dynamic Programming based solution. In the following solution, an additional field ‘liss’ is added to tree nodes. The initial value of ‘liss’ is set as 0 for all nodes. The recursive function LISS() calculates ‘liss’ for a node only if it is not already set.
[pastacode lang=”c” manual=”%2F*%20Dynamic%20programming%20based%20program%20for%20Largest%20Independent%20Set%20problem%20*%2F%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%20%0A%2F%2F%20A%20utility%20function%20to%20find%20max%20of%20two%20integers%0Aint%20max(int%20x%2C%20int%20y)%20%7B%20return%20(x%20%3E%20y)%3F%20x%3A%20y%3B%20%7D%0A%20%0A%2F*%20A%20binary%20tree%20node%20has%20data%2C%20pointer%20to%20left%20child%20and%20a%20pointer%20to%20%0A%20%20%20right%20child%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20int%20liss%3B%0A%20%20%20%20struct%20node%20*left%2C%20*right%3B%0A%7D%3B%0A%20%0A%2F%2F%20A%20memoization%20function%20returns%20size%20of%20the%20largest%20independent%20set%20in%0A%2F%2F%20%20a%20given%20binary%20tree%0Aint%20LISS(struct%20node%20*root)%0A%7B%0A%20%20%20%20if%20(root%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%0A%20%20%20%20if%20(root-%3Eliss)%0A%20%20%20%20%20%20%20%20return%20root-%3Eliss%3B%0A%20%0A%20%20%20%20if%20(root-%3Eleft%20%3D%3D%20NULL%20%26%26%20root-%3Eright%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20return%20(root-%3Eliss%20%3D%201)%3B%0A%20%0A%20%20%20%20%2F%2F%20Calculate%20size%20excluding%20the%20current%20node%0A%20%20%20%20int%20liss_excl%20%3D%20LISS(root-%3Eleft)%20%2B%20LISS(root-%3Eright)%3B%0A%20%0A%20%20%20%20%2F%2F%20Calculate%20size%20including%20the%20current%20node%0A%20%20%20%20int%20liss_incl%20%3D%201%3B%0A%20%20%20%20if%20(root-%3Eleft)%0A%20%20%20%20%20%20%20%20liss_incl%20%2B%3D%20LISS(root-%3Eleft-%3Eleft)%20%2B%20LISS(root-%3Eleft-%3Eright)%3B%0A%20%20%20%20if%20(root-%3Eright)%0A%20%20%20%20%20%20%20%20liss_incl%20%2B%3D%20LISS(root-%3Eright-%3Eleft)%20%2B%20LISS(root-%3Eright-%3Eright)%3B%0A%20%0A%20%20%20%20%2F%2F%20Maximum%20of%20two%20sizes%20is%20LISS%2C%20store%20it%20for%20future%20uses.%0A%20%20%20%20root-%3Eliss%20%3D%20max(liss_incl%2C%20liss_excl)%3B%0A%20%0A%20%20%20%20return%20root-%3Eliss%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20create%20a%20node%0Astruct%20node*%20newNode(int%20data)%0A%7B%0A%20%20%20%20struct%20node*%20temp%20%3D%20(struct%20node%20*)%20malloc(%20sizeof(struct%20node)%20)%3B%0A%20%20%20%20temp-%3Edata%20%3D%20data%3B%0A%20%20%20%20temp-%3Eleft%20%3D%20temp-%3Eright%20%3D%20NULL%3B%0A%20%20%20%20temp-%3Eliss%20%3D%200%3B%0A%20%20%20%20return%20temp%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Let%20us%20construct%20the%20tree%20given%20in%20the%20above%20diagram%0A%20%20%20%20struct%20node%20*root%20%20%20%20%20%20%20%20%20%3D%20newNode(20)%3B%0A%20%20%20%20root-%3Eleft%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3D%20newNode(8)%3B%0A%20%20%20%20root-%3Eleft-%3Eleft%20%20%20%20%20%20%20%20%20%20%3D%20newNode(4)%3B%0A%20%20%20%20root-%3Eleft-%3Eright%20%20%20%20%20%20%20%20%20%3D%20newNode(12)%3B%0A%20%20%20%20root-%3Eleft-%3Eright-%3Eleft%20%20%20%3D%20newNode(10)%3B%0A%20%20%20%20root-%3Eleft-%3Eright-%3Eright%20%20%3D%20newNode(14)%3B%0A%20%20%20%20root-%3Eright%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3D%20newNode(22)%3B%0A%20%20%20%20root-%3Eright-%3Eright%20%20%20%20%20%20%20%20%3D%20newNode(25)%3B%0A%20%0A%20%20%20%20printf%20(%22Size%20of%20the%20Largest%20Independent%20Set%20is%20%25d%20%22%2C%20LISS(root))%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”C” highlight=”” provider=”manual”/]Output :
Size of the Largest Independent Set is 5
Time Complexity: O(n) where n is the number of nodes in given Binary tree.
Following extensions to above solution can be tried as an exercise.
- Extend the above solution for n-ary tree.
- The above solution modifies the given tree structure by adding an additional field ‘liss’ to tree nodes. Extend the solution so that it doesn’t modify the tree structure.
- The above solution only returns size of LIS, it doesn’t print elements of LIS. Extend the solution to print all nodes that are part of LIS.