Sum of Leaf nodes of a tree
Problem-Given a binary tree.Our task is to find the sum of all leaf nodes.
Approach-Problem can be easily solved by using DFS traversal of a tree.
//code starts here
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
};
int sumLeaf(Node* root)
{
if(root==NULL)
{
return 0; }
if(root->left==NULL && root->right ==NULL)
{
return root->data;
}
return (sumLeaf(root->left)+sumLeaf(root->right));
}
struct Node* buildTree(int* preorder,int* inorder,int inorder_start,int inorder_end,int preorder_start,int preorder_end){
if(inorder_start>inorder_end){
return NULL;
}
int search=preorder[preorder_start];
int index=-1;
for(int y=inorder_start;y<=inorder_end;y++){
if(inorder[y]==search){
index=y;
break;
}
}
int left_inorder_start=inorder_start;
int left_inorder_end=index-1;
int left_preOrder_start=preorder_start+1;
int left_preOrder_end = (left_inorder_end-left_inorder_start)+left_preOrder_start;
int right_inorder_start=index+1;
int right_inorder_end=inorder_end;
int right_preOrder_start=left_preOrder_end+1;
int right_preOrder_end=preorder_end;
struct Node* root = (struct Node*)malloc(sizeof(struct Node));
root->data=preorder[preorder_start];
root->left=buildTree(preorder,inorder,left_inorder_start,left_inorder_end,left_preOrder_start,left_preOrder_end);
root->right=buildTree(preorder,inorder,right_inorder_start,right_inorder_end,right_preOrder_start,right_preOrder_end);
return root;
}
int main(){
cout<<"Enter the size of the Tree "<<endl;
int siz;
cin>>siz;
int in[siz];
int pre[siz];
cout<<"Enter the Inorder Traversal of the Tree "<<endl;
for(int y=0;y< siz ;y++){
cin>>in[y];
}
cout<<"Enetr the PreOrder traversal of thre Tree "<<endl;
for(int h =0;h<siz;h++){
cin>>pre[h];
}
struct Node* r=buildTree(pre,in,0,(siz-1),0,(siz-1));
//The r is the root
int sum=sumLeaf(r);
cout<<sum;
return ;
}
// Code ends here....
Comments