C Program to Find the Largest Independent Set in Binary Tree

«
»
This is a C Program to find the size of largest independent set in a given binary tree. 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.

Here is source code of the C Program to Find the Maximum Independent Set of a Tree in Linear Time. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* Dynamic programming based program for Largest Independent Set problem */
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. // A utility function to find max of two integers
  6. int max(int x, int y) {
  7.     return (x > y) ? x : y;
  8. }
  9.  
  10. /* A binary tree node has data, pointer to left child and a pointer to
  11.  right child */
  12. struct node {
  13.     int data;
  14.     int liss;
  15.     struct node *left, *right;
  16. };
  17.  
  18. // A memoization function returns size of the largest independent set in
  19. //  a given binary tree
  20. int LISS(struct node *root) {
  21.     if (root == NULL)
  22.         return 0;
  23.  
  24.     if (root->liss)
  25.         return root->liss;
  26.  
  27.     if (root->left == NULL && root->right == NULL)
  28.         return (root->liss = 1);
  29.  
  30.     // Caculate size excluding the current node
  31.     int liss_excl = LISS(root->left) + LISS(root->right);
  32.  
  33.     // Calculate size including the current node
  34.     int liss_incl = 1;
  35.     if (root->left)
  36.         liss_incl += LISS(root->left->left) + LISS(root->left->right);
  37.     if (root->right)
  38.         liss_incl += LISS(root->right->left) + LISS(root->right->right);
  39.  
  40.     // Return the maximum of two sizes
  41.     root->liss = max(liss_incl, liss_excl);
  42.  
  43.     return root->liss;
  44. }
  45.  
  46. // A utility function to create a node
  47. struct node* newNode(int data) {
  48.     struct node* temp = (struct node *) malloc(sizeof(struct node));
  49.     temp->data = data;
  50.     temp->left = temp->right = NULL;
  51.     temp->liss = 0;
  52.     return temp;
  53. }
  54.  
  55. // Driver program to test above functions
  56. int main() {
  57.     // Let us construct the tree given in the above diagram
  58.     struct node *root = newNode(20);
  59.     root->left = newNode(8);
  60.     root->left->left = newNode(4);
  61.     root->left->right = newNode(12);
  62.     root->left->right->left = newNode(10);
  63.     root->left->right->right = newNode(14);
  64.     root->right = newNode(22);
  65.     root->right->right = newNode(25);
  66.  
  67.     printf("Size of the Largest Independent Set is %d ", LISS(root));
  68.  
  69.     return 0;
  70. }

Output:

$ gcc LargestIndependentSetLinearTime.c
$ ./a.out
 
Size of the Largest Independent Set is 5

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.