Friday, March 23, 2012

Subtree in a BST with maximum sum

Find a sub tree in a BST such that the sub tree has maximum sum.

Strategy:
Sum of a tree is the sum of all the nodes of that tree. We have to find a sub-tree whose sum is maximum. Clearly, this tree has negative elements as well otherwise the question is trivial and the original tree itself is the answer.
 
Code:
#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

//typedef tree node;

void insert(struct node *& root,int item){
     if(root==NULL){
          struct node *r= (struct node*)malloc(sizeof(struct node));
          r->data=item;
          r->left=NULL;
          r->right=NULL;
          root=r;
          return;
     }
     if (item< root->data){
        insert(root->left,item);
        return;
     }
     else{
        insert(root->right,item);
        return;
     }
     return;
}

int maxSum(struct node* root, int* max)
{
    if(root == NULL)
        return 0;

    int sum = maxSum(root->left, max) + maxSum(root->right, max) + root->data;

    if(sum > *max)
        *max = sum;

    return sum;
}

int main()
{
    struct node *root=NULL;

    insert(root, -10);
    insert(root, -20);
    insert(root, 30);
    insert(root, -5);
    insert(root, 40);

    int max=0;

    maxSum(root, &max);
    printf("maxSum = %d\n", max);

    return 0;
}

3 comments:

  1. When I ran your code it printed 65 instead of 70 which I had expected to be printed.

    ReplyDelete
    Replies
    1. @Coder:The answer should be 65 and NOT 70 as i suppose.The question is about finding a SUBTREE i.e.including all its descendants.T hat means subtree at 30 cant exclude child -5.

      Delete
    2. in the void insert function why did you use struct node *& root

      Delete