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.

/* Dynamic programming based program for 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;
```
```
    int liss;
```
```
    struct node *left, *right;
```
```
};
```
```
 
```

// A memoization function returns size of the largest independent set in

```
//  a given binary tree
```
```
int 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;
```
```
}
```
```
 
```
```
// 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;
```
```
    temp->liss = 0;
```
```
    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 LargestIndependentSetLinearTime.c
$ ./a.out
 
Size of the Largest Independent Set is 5

Sanfoundry Global Education & Learning Series – 1000 C Programs.

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

« Prev - C Program to Implement Levenshtein Distance Computing Algorithm

» Next - C Program to Implement Knuth-Morris-Pratt Algorithm for Pattern Searching

Related Posts:

Recommended Articles: