### [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.

1. 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;
}
}

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

3. // 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;

}
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;
}