We can use post-order traversal to find the sum of left and right subtree and sum of leftsum + rightsum +rootdata is passed above to the parent of tree. Maintain a node to root of largest subtree found so far and update it whenver greater sum is found. Bottom-up approach.Time complexity-O(n).Stack space-O(n) Node *maxSumSubtree(Node *root) { if(!root) return NULL; if(isleaf(root)) return root; int maxsum=0; Node *res=NULL; helper(root,&res,&maxsum); return *res; } int helper(Node *p,Node **res,int *maxSum) { if(!p) return 0; int lsum = helper(p->left,res,maxsum); int rsum = helper(p->right,res,maxsum); int total = lsum + rsum + p->data; if( total > *maxsum ){ *maxsum=total; *res=p; } return total; }

// A program to check if a given binary tree is complete or not #include #include #include

/* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; };

int findmax(int a, int b) { if(a>=b) return a; else return b; }

int findMaxSubtreeUtil(struct node *root, int *maxsum, struct node **maxnode) { int max =INT_MIN,left=INT_MIN,right=INT_MIN; int temp = INT_MIN; // base case if(root == NULL) return INT_MIN;

left= findMaxSubtreeUtil(root->left,maxsum,maxnode); right = findMaxSubtreeUtil(root->right,maxsum,maxnode);

// find max(left child, right child) if(left>right) { *maxnode = root->left; max = left; } else if(leftright; max = right; }

// both child present if(left!=INT_MIN && right!=INT_MIN) temp = root->data+left+right; // only left child present else if(left != INT_MIN && right==INT_MIN) temp = root->data+left; // only right child present else if(left == INT_MIN && right!=INT_MIN) temp = root->data+right; // leaf node else if (left == INT_MIN && right==INT_MIN) temp = root->data;

// findmax(temp,max) and update maxsum and maxnode accordingly if(temp > max) { *maxnode = root; if(temp> *maxsum) *maxsum = temp;

/* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL;

return(node); }

/* Driver program to test above functions*/ int main() { // Let us create binary tree given in the above example struct node *root = newNode(1); root->left = newNode(-6); root->right = newNode(-8); root->left->left = newNode(12); root->left->right = newNode(13); root->right->left = newNode(2); root->right->right = newNode(4); findMaxSubtree(root); return 0; }

Implement a function getbits, that returns the(right adjusted) n bits that begin at position p of an integer. Assume bit position 0 is at the right end and that n and p are sensible positive values.

You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.

We can use post-order traversal to find the sum of left and right subtree

ReplyDeleteand sum of leftsum + rightsum +rootdata is passed above to the parent of tree.

Maintain a node to root of largest subtree found so far and update it whenver greater sum is found.

Bottom-up approach.Time complexity-O(n).Stack space-O(n)

Node *maxSumSubtree(Node *root)

{

if(!root) return NULL;

if(isleaf(root)) return root;

int maxsum=0;

Node *res=NULL;

helper(root,&res,&maxsum);

return *res;

}

int helper(Node *p,Node **res,int *maxSum)

{

if(!p) return 0;

int lsum = helper(p->left,res,maxsum);

int rsum = helper(p->right,res,maxsum);

int total = lsum + rsum + p->data;

if( total > *maxsum ){

*maxsum=total;

*res=p;

}

return total;

}

@naveen yes very nice explanation using bottom up approach is little tricky to think and implement, but your solution is neat...

ReplyDelete// A program to check if a given binary tree is complete or not

ReplyDelete#include

#include

#include

/* A binary tree node has data, pointer to left child

and a pointer to right child */

struct node

{

int data;

struct node* left;

struct node* right;

};

int findmax(int a, int b)

{

if(a>=b)

return a;

else

return b;

}

int findMaxSubtreeUtil(struct node *root, int *maxsum, struct node **maxnode)

{

int max =INT_MIN,left=INT_MIN,right=INT_MIN;

int temp = INT_MIN;

// base case

if(root == NULL)

return INT_MIN;

left= findMaxSubtreeUtil(root->left,maxsum,maxnode);

right = findMaxSubtreeUtil(root->right,maxsum,maxnode);

// find max(left child, right child)

if(left>right)

{

*maxnode = root->left;

max = left;

}

else if(leftright;

max = right;

}

// both child present

if(left!=INT_MIN && right!=INT_MIN)

temp = root->data+left+right;

// only left child present

else if(left != INT_MIN && right==INT_MIN)

temp = root->data+left;

// only right child present

else if(left == INT_MIN && right!=INT_MIN)

temp = root->data+right;

// leaf node

else if (left == INT_MIN && right==INT_MIN)

temp = root->data;

// findmax(temp,max) and update maxsum and maxnode accordingly

if(temp > max)

{

*maxnode = root;

if(temp> *maxsum)

*maxsum = temp;

}

return temp;

}

void findMaxSubtree(struct node *root)

{

int maxsum = INT_MIN;

struct node *maxnode = NULL;

findMaxSubtreeUtil(root,&maxsum,&maxnode);

if(maxsum!=INT_MAX)

printf("maxsum: %d, maxNode->data: %d",maxsum,maxnode->data);

else

printf("no node found");

}

/* Helper function that allocates a new node with the

given data and NULL left and right pointers. */

struct node* newNode(int data)

{

struct node* node = (struct node*)

malloc(sizeof(struct node));

node->data = data;

node->left = NULL;

node->right = NULL;

return(node);

}

/* Driver program to test above functions*/

int main()

{

// Let us create binary tree given in the above example

struct node *root = newNode(1);

root->left = newNode(-6);

root->right = newNode(-8);

root->left->left = newNode(12);

root->left->right = newNode(13);

root->right->left = newNode(2);

root->right->right = newNode(4);

findMaxSubtree(root);

return 0;

}