top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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

+2 votes
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 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+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);

}

if there is any problem to understand the concept leave a comment in comment section.
i have assumed tree as
enter image description here

answer Jul 3, 2016 by Shahsikant Dwivedi
Similar Questions
0 votes

How to find longest consecutive path in a binary tree using C/C++/Java?

+2 votes

Given a binary tree where each node has some weight. You have to return the max weight in the binary tree.

+4 votes

Given a binary tree, print all its root to leaf paths with recursion. For example, consider the following Binary Tree,
enter image description here

complexity must be O(n) or O(nlogn).

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...