[AMAZON] Subtree with largest sum
Given a binary tree, every node has a int value, return the root node of subtree with the largest sum up value.
Given an integer n, write a function that returns count of trailing zeroes in n!. Examples: Input: n = 5 Output: 1 Factorial of 5 is 20 which has one trailing 0. Input: n = 20 Output: 4 Factorial of 20 is 2432902008176640000 which has 4 trailing zeroes. Input: n = 100 Output: 24
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;
}