#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
A blog on programming and software design interview problems and solutions. Also there are some application development related stuff.
Pages
Tuesday, December 4, 2012
Find the Largest Sum Path from root to leaf in a binary tree
Subscribe to:
Posts (Atom)