Root to leaf path sum equal to a given number

Root to leaf path sum equal to a given number

#include <stdio.h> #include <stdlib.h> /* structure of a tree node */ struct node { int data; struct node *left,*right; }; /* function to create a newnode with left & right child as NULL */ struct node* newnode(int data) { struct node *temp=(struct node*)malloc(sizeof(struct node)); temp->data=data; temp->left=temp->right=NULL; return temp; } /* insert function to insert a node in a binary search tree */ struct node* insert(struct node *root,int data) { if(root==NULL) return newnode(data); /* if the data to be inserted is less than the data of the root, recur for left & insert the node as appropriate leaf */ if(data < root->data) root->left=insert(root->left,data); /* recur for right & insert the node, if it is greater than the root node */ else root->right=insert(root->right,data); return root; } /* do an inorder traversal. i.e., nodes are printed in the order: 1. left node 2. root node 3. right node */ void inorder(struct node *root) { if(root==NULL) return; inorder(root->left); printf("%d ",root->data); inorder(root->right); } /* check whether the current root to leaf path has the sum equals the given sum */ int checksumpath(int *path,int n,int sum) { int pathsum=0; for(--n;n>=0;n--) pathsum += *(path+n); return (pathsum==sum); } /* print the current path , if the sum matches */ void printpath(int *path,int n) { int i; for(i=0;i<n;i++) printf("%d ",*(path+i)); printf("\n"); } /* find the appropriate root to leaf path if the sum of nodes in the path equals the given sum */ void rootleafpath(struct node *root,int *path,int pathlen,int sum) { if(root==NULL) return; /* add the current node to the path array */ *(path+pathlen)=root->data; pathlen++; /* if we reach a leaf node, check whether the path sum equals the given sum */ if(root->left==NULL && root->right==NULL) { if(checksumpath(path,pathlen,sum)) /* if it does, print the current path */ printpath(path,pathlen); } else { rootleafpath(root->left,path,pathlen,sum); rootleafpath(root->right,path,pathlen,sum); } } int main(void) { struct node *root=NULL; int *path,pathlen=0,sum; /* allocate memory for the path array */ path=(int*)malloc(sizeof(int)*1000); /* insert the nodes in the binary search tree */ root=insert(root,5); insert(root,3); insert(root,7); insert(root,4); insert(root,2); insert(root,1); insert(root,6); insert(root,8); //inorder(root); /* get the sum from the user for which we have to check the root to leaf path sum that equals the given sum */ scanf("%d",&sum); rootleafpath(root,path,pathlen,sum); return 0; }