[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;
    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 ){
    return total;

  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

    /* 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)
    return a;
    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)
    *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;

    printf("maxsum: %d, maxNode->data: %d",maxsum,maxnode->data);
    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;


    /* 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);
    return 0;


Post a Comment

Popular posts from this blog