Tuesday, December 4, 2012

Find the Largest Sum Path from root to leaf in a binary tree


#include<iostream>
#define SMALL -999999
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
struct node* parent;
};
struct node* createnode(int x)
{
struct node* new_node=new struct node;
new_node->data=x;
new_node->left=NULL;
new_node->right=NULL;
new_node->parent=NULL;
return new_node;
}
void parentfinder(node *root,node *parent)
{
if(root)
{
root->parent=parent;
parent=root;
parentfinder(root->left,parent);
parentfinder(root->right,parent);
}
return;
}
int height(struct node* root)
{
if(root==NULL)
{
return 0;
}
else
{
int lheight=1+height(root->left);
int rheight=1+height(root->right);
return lheight>rheight?lheight:rheight;
}
}
void levelorderprint(struct node* root,int level)
{
if(root && level==0)
{
cout<<root->data<<"->";
if(root->parent)
{
cout<<root->parent->data<<endl;
}
}
else if(root)
{
levelorderprint(root->left,level-1);
levelorderprint(root->right,level-1);
}
}
void levelorder(struct node* root)
{
int h=height(root);
for(int i=0;i<h;i++)
{
levelorderprint(root,i);
cout<<endl;
}
}
struct node** summer(node *root,node **maximum,node *parent)
{
if(root)
{
if(parent)
{
root->data=root->data+parent->data;
if((*maximum)->data<root->data)
{
*maximum=root;
}
}
parent=root;
summer(root->left,maximum,parent);
summer(root->right,maximum,parent);
}
return maximum;
}
int searchformax(node *root,node **max,bool *found,int A[100])
{
static int i=0;
if(root)
{
if(root==*max)
{
*found=true;
}
if(!(*found))
{
searchformax(root->left,max,found,A);
if(!(*found))
{
searchformax(root->right,max,found,A);
}
}
if(*found)
{
A[i]=root->data;
i++;
}
}
return i;
}
int main()
{
struct node* root=createnode(1);
root->left=createnode(2);
root->right=createnode(3);
root->left->right=createnode(4);
root->left->left=createnode(5);
root->right->right=createnode(-6);
root->right->left=createnode(7);
root->right->right->left=createnode(8);
//root->right->right->left->left=createnode(10);
root->right->right->right=createnode(10);
parentfinder(root,NULL);
levelorder(root);
node *ptr=new struct node;
ptr->data=SMALL;
node **max=&ptr;
max = summer(root,max,NULL);
bool var=false;
bool *found = &var;
int A[100];
int count=searchformax(root,max,found,A);
for(int i=0;i<count-1;i++)
{
A[i]=A[i]-A[i+1];
}
cout<<"The path is:"<<endl;
while(count--)
{
cout<<A[count]<<endl;
}
}
Output:
1->
2->1
3->1

5->2
4->2
7->3
-6->3

8->-6
10->-6

The maximum sum path is:
1
3
7