# Find the smallest weight path between root and any leaf node?

133 views

Say you are given a tree and weight is calculated by sum of values in the nodes in that path.

posted Mar 14, 2016

+1 vote

Idea is to trace each individual leaf from root node and calculate it's weight recursively , print the least weight among them.
rootToLeaf function saves trace from root to each individual leaf node in an Array A, there is a line "printf("%d ",p[j]);" in print() function which i have disabled you can enable it and see the respective traversal.

``````#include<bits/stdc++.h>
int A[100];
int i=0;
int Sum=0,minSum=328664;
struct node{
struct node *left,*right;
int data;
};
typedef struct node node;

node *newNode(int data){
node *temp;
temp=(node *) malloc(sizeof(node));
temp->left=temp->right=NULL;
temp->data=data;
return temp;
}

void print(int *p){
if(i>0){
int j;
for(j=0;j<i;j++){
// printf("%d ",p[j]);
Sum+=p[j];
}
if(Sum<minSum)
minSum=Sum;
}
else
return;
}
void rootToLeaf(node *root){
if(root){
A[i++]=root->data;
rootToLeaf(root->left);
//printf("%d ",root->data);
rootToLeaf(root->right);
if(root->left==NULL && root->right==NULL)
print(A);
i--;
}
}
int main(){
node * root;
root=newNode(6);
root->left=newNode(3);
root->right=newNode(5);
root->right->right=newNode(4);
root->left->left=newNode(2);
root->left->right=newNode(5);
root->left->right->left=newNode(7);
root->left->right->right=newNode(4);
rootToLeaf(root);
printf("minimum weight from root to leaf is=%d\n",minSum);

}
``````

i have assumed tree as

Similar Questions