Dynamic Programming | Set 26 (Largest Independent Set Problem) | GeeksforGeeks
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.
Recursive version - not efficient
Read full article from Dynamic Programming | Set 26 (Largest Independent Set Problem) | GeeksforGeeks
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.
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.
Time Complexity: O(n)
struct node{ int data; int liss; struct node *left, *right;};// A memoization function returns size of the largest independent set in// a given binary treeint LISS(struct node *root){ if (root == NULL) return 0; if (root->liss) return root->liss; if (root->left == NULL && root->right == NULL) return (root->liss = 1); // Caculate size excluding the current node int liss_excl = LISS(root->left) + LISS(root->right); // Calculate size including the current node int liss_incl = 1; if (root->left) liss_incl += LISS(root->left->left) + LISS(root->left->right); if (root->right) liss_incl += LISS(root->right->left) + LISS(root->right->right); // Return the maximum of two sizes root->liss = max(liss_incl, liss_excl); return root->liss;}Recursive version - not efficient
int LISS(struct node *root){ if (root == NULL) return 0; // Caculate size excluding the current node int size_excl = LISS(root->left) + LISS(root->right); // Calculate size including the current node int size_incl = 1; if (root->left) size_incl += LISS(root->left->left) + LISS(root->left->right); if (root->right) size_incl += LISS(root->right->left) + LISS(root->right->right); // Return the maximum of two sizes return max(size_incl, size_excl);}