C++ Program to Find Size of the Largest Independent Set(LIS) in a Given a Binary Tree

This is a C++ Program to Find Size of the Largest Independent Set (LIS) in a Given a Binary Tree.

Algorithm

Begin.    Create a structure n to declare data d, a left child pointer l and a right child pointer r.    Call a function max() to return maximum between two integers. Create a function LIS() to return the    size of the largest independent set in a given binary tree.    Calculate size excluding the current node    int size_excl = LIS(root->l) + LIS(root->r)    Calculate size including the current node    int size_incl = 1;    if (root->l)       size_incl += LIS(root->l->l) + LIS(root->l->r)    if (root->right)       size_incl += LIS(root->r->l) + LIS(root->r->r)       Return the maximum of two sizes       Create a function to create newnode. End.

Example Code

 Live Demo

#include <iostream> using namespace std; struct n {    int d;    int lis;    struct n *l, *r; }; int max(int x, int y) {    return (x > y) ? x : y; } int LIS(struct n *root) {    if (root == NULL)       return 0;    if (root->lis)       return root->lis;    if (root->l == NULL && root->r == NULL)       return (root->lis = 1);       int lis_excl = LIS(root->l) + LIS(root->r);       int lis_incl = 1;    if (root->l)       lis_incl += LIS(root->l->l) + LIS(root->l->r);    if (root->r)       lis_incl += LIS(root->r->l) + LIS(root->r->r);       root->lis = max(lis_incl, lis_excl);       return root->lis; } struct n* newnode(int d) {    struct n* t = (struct n *) malloc(sizeof(struct n));    t->d = d;    t->l = t->r = NULL;    t->lis = 0;    return t; } int main() {    struct n *root = newnode(30);    root->l= newnode(20);    root->l->l = newnode(10);    root->l->r = newnode(7);    root->l->r->l = newnode(9);    root->l->r->r = newnode(6);    root->r = newnode(50);    root->r->r = newnode(26);    cout<<"Size of the Largest Independent Set is "<< LIS(root);    return 0; }

Output

Size of the Largest Independent Set is 5