Root to leaf path sum equal to a given number
we have to calculate the path sum means the sum of each node in the path for every leaf node.
ex-
leaf node 1 is having path 15>10>1 so sum is 26
leaf node 14 is having path 15>10>13>14 so sum is 52
#include <stdio.h>
#include <stdlib.h>
struct btnode
{
int value;
struct btnode *l;
struct btnode *r;
}*root = NULL, *temp = NULL, *t2, *t1;
void create()
{
int data;
printf("Enter data of node to be inserted : ");
scanf("%d", &data);
temp = (struct btnode *)malloc(1*sizeof(struct btnode));
temp->value = data;
temp->l = temp->r = NULL;
}
void search(struct btnode *t)
{
if ((temp->value > t->value) && (t->r != NULL))
search(t->r);
else if ((temp->value > t->value) && (t->r == NULL))
t->r = temp;
else if ((temp->value < t->value) && (t->l != NULL))
search(t->l);
else if ((temp->value < t->value) && (t->l == NULL))
t->l = temp;
}
void insert()
{
create();
if (root == NULL)
root = temp;
else
search(root);
}
void inorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
if (t->l != NULL)
inorder(t->l);
printf("%d -> ", t->value);
if (t->r != NULL)
inorder(t->r);
}
int size(struct btnode* root)
{
if(root->l==NULL&& root->r==NULL)
return 1;
if(root->l!=NULL && root->r==NULL)
return 1+size(root->l);
if(root->r!=NULL && root->l==NULL)
return 1+size(root->r);
return (size(root->l)+size(root->r))+1;
}
int print_root_to_leaf_sum(struct btnode* root, int sum)
{
if(root->l!=NULL)
{
sum=sum+root->value;
print_root_to_leaf_sum(root->l,sum);
}
if(root->r!=NULL)
{
print_root_to_leaf_sum(root->r,sum);
sum=sum+root->value;
}
if(root->l==NULL && root->r==NULL)
{
sum=sum+root->value;
printf("the sum of path ==>%d\n",sum);
}
}
int main()
{
int ch;
int a1,a2;
while(1)
{
printf("\n");
printf("OPERATIONS ---\n");
printf("1.Insert an element into tree\n");
printf("2.Inorder Traversal\n");
printf("3.root to leaf sum\n");
printf("4 Exit\n");
printf("Enter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert();
break;
case 2:
inorder(root);
break;
case 3:
print_root_to_leaf_sum(root,0);
break;
case 4:
exit(0);
default :
printf("Wrong choice, Please enter correct choice ");
break;
}
}
return 0;
}
No comments:
Post a Comment