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;
}
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;
}
When I ran your code it printed 65 instead of 70 which I had expected to be printed.
ReplyDelete@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.
Deletein the void insert function why did you use struct node *& root
Delete