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.
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 Size of the Largest Independent Set(LIS) in a Given a Binary Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
// A naive recursive implementation of Largest Independent Set problem
#include <stdio.h>
#include <stdlib.h>
// A utility function to find max of two integers
int max(int x, int y) {
return (x > y) ? x : y;
}
/* A binary tree node has data, pointer to left child and a pointer to
right child */
struct node {
int data;
struct node *left, *right;
};
// The function returns size of the largest independent set in a given
// binary tree
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);
}
// A utility function to create a node
struct node* newNode(int data) {
struct node* temp = (struct node *) malloc(sizeof(struct node));
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver program to test above functions
int main() {
// Let us construct the tree given in the above diagram
struct node *root = newNode(20);
root->left = newNode(8);
root->left->left = newNode(4);
root->left->right = newNode(12);
root->left->right->left = newNode(10);
root->left->right->right = newNode(14);
root->right = newNode(22);
root->right->right = newNode(25);
printf("Size of the Largest Independent Set is %d ", LISS(root));
return 0;
}
Output:
$ gcc LargestIndependentSetBinaryTree.c $ ./a.out Size of the Largest Independent Set is 5
Sanfoundry Global Education & Learning Series – 1000 C Programs.
advertisement
advertisement
Here’s the list of Best Books in C Programming, Data Structures and Algorithms.
Next Steps:
- Get Free Certificate of Merit in C Programming
- Participate in C Programming Certification Contest
- Become a Top Ranker in C Programming
- Take C Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Related Posts:
- Apply for Computer Science Internship
- Apply for C Internship
- Practice Computer Science MCQs
- Buy C Books
- Practice BCA MCQs