Root to leaf path sum in a Binary tree in C++

In this tutorial, we will learn about how to find the root to leaf path sum in a binary tree. We will also see the recursive code implementation in C++.

We will also see the example to understand the concept in a better way.

Root to Leaf Path Sum in Binary tree

In root to leaf path sum problem, we have to find the sum of all the numbers formed from root to leaf paths.

Let’s consider the example to understand the concept,

                           1
                         /   \ 
                        2     3 
                      /  \   / \
                    4     5  6  7  
                     

 4 leaves, hence 4 root to leaf paths:
Path Number
1->2->4 ==124
1->2->5 == 125
1->3->6 == 136
1->3->7 == 137 
Answer = 124+125+136+137=522.

Hence, we can understand the root to leaf path sum problem in above example.

We will use the recursion to find the solution to this given problem.

Now, let’s see the pseudocode,

find(Node* root,long long val)
    if root==NULL then do 
       return 0;
    then update val=(val*10)+root->data;
    if root->left==NULL&&root->right==NULL then do
       return val;
    return find(root->left,val)+find(root->right,val);

Now, let’s see the C++ code:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
//structure of Node
struct Node{
  int data;
  Node* left;
  Node* right;
};
//function to create the node
Node* create(int x){
  Node* temp=new Node;
  temp->data=x;
  temp->left=NULL;
  temp->right=NULL;
  return temp;
}
//funtion to find root to leaf path sum
int find(Node* root,long long val){
    if(root==NULL)return 0;
    val=(val*10)+root->data;
    if(root->left==NULL&&root->right==NULL)return val;
    return find(root->left,val)+find(root->right,val);
}
long long treePathsSum(Node *root)
{
    long long val=0;
    return find(root,val);
}
//main fuction
int main(){
  Node* root=create(1);
  root->left=create(2);
  root->left->right=create(5);
  root->left->left=create(4);
  root->right=create(3);
  root->right->left=create(6);
  root->right->right=create(7);
    cout<<"root to leaf path sum is:"<<" ";
    cout<<treePathsSum(root);
    return 0;
}

Output

The output of our program is given below:

root to leaf path sum is: 522

In the above code, we firstly traverse left subtree and then right subtree for each node till we not found leaf node and for each traversal, we store the number formed by digits in variable int val. Let’s see For left path of root 1->2->4, each time VAL is incremented by VAL*10 + Node->data and return VAL when we found a leaf node in this path. Then before each new path traversal VAL is initialised to 0 and perform the same step for update the VAL for each new path traversal.

You may also learn,

Top view of binary tree in C++

Bottom view of the binary tree in C++

Boundary traversal of the Binary tree in C++