Ronzii's Blog

Just your average geek's blog

Maximum Sum in a Tree

#include <iostream>
#include <climits>
using namespace std;
struct node
{
    int value;
    struct node *left;
    struct node *right;
};
typedef struct node TreeNode;
int treeMin = INT_MAX;
TreeNode* createNode(int n)
{
    TreeNode *temp = new TreeNode;
    temp->value = n;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
int max5(int a, int b,int c, int d, int e)
{
    return max(a,max(b,max(c,max(d,e))));
}
int maxSumTree(TreeNode* current, int* sum)
{
    if(current==NULL)
    {
        *sum = treeMin;
        return treeMin;
    }
    else
    {
        int ls = INT_MIN,rs = INT_MIN;
        int l = maxSumTree(current->left,&ls);
        int r = maxSumTree(current->right,&rs);
        *sum = max5(*sum,current->value, ls+rs+current->value,ls+current->value,rs+current->value);
        return max(*sum,max(l,r));
    }
}

void binaryTreeMin(TreeNode* current)
{
    if(current==NULL)   return;
    binaryTreeMin(current->left);
    if(treeMin>current->value)
        treeMin = current->value;
    binaryTreeMin(current->right);
}
int main()
{
    TreeNode* root = createNode(17);
    root->left = createNode(15);
    root->right = createNode(-20);
    root->left->left  = createNode(13);
    root->left->left->left  = createNode(-15);
    root->left->left->right  = createNode(-7);
    root->right->left  = createNode(50);
    root->right->right  = createNode(-72);
    binaryTreeMin(root);
    int sum = treeMin;
    cout<<maxSumTree(root,&sum);
    return 0;
}
Advertisements

March 31, 2012 - Posted by | C++ | , , , , ,

1 Comment »

  1. Thanks for sharing.

    Comment by AndroidResearch | March 31, 2012 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s