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

Comments

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

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

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

    ReplyDelete

Post a Comment

Popular posts from this blog