# Sum of all numbers formed by root to leaf path

In this article, we are going to see how to calculate root to leaf path sums? This problem has been featured in Google interview.
Submitted by Radib Kar, on March 28, 2019

Problem statement:

Given a binary tree, where every node value is a number between 0-9. Find the sum of all the numbers which are formed from root to leaf paths.

Example: All possible roots to leaf paths in this tree are:

```    8->5->9 //number formed=859
8->5->7->1 //number formed=8571
8->5->7->2->2 //number formed=85722
8->4->1->3//number formed=8413

Sum: 859+8571+85722+8413=103565
```

Solution:

The idea is quite similar as we did for the problem all root to leaf paths (read: All root to leaf paths

Here instead of printing them we are forming a number from the digits on the path and storing the numbers for addition.

Algorithm:

Pre-requisite:

Input binary tree root, list a, stack st

```    FUNCTION printpathrecursively(Node* current_node, list  a){
1.  base case
IF(current_node ==NULL)
return;
END IF
2.  pushcurrent_node ->data to the stack;
IF current_node is leaf node //leaf node reached
Form number from the digits stored in the stack st
Append the formed number to the list a
END IF
3.  printpathrecursively(current_node ->left,a);//recur for left subtree
printpathrecursively(current_node ->right,a);//recur for right subtree
END FUNCTION
```

Sum all the numbers stored in the list a and print it.

N.B: Remember here the list parameter must be passed by reference to store all the numbers formed from the digits on the root-to-leaf path

In the main function create an empty list a, and call printpathrecursively(root, a, st);

Example with explanation: ```    In main we call printpathrecursively(root, a, st)
---------------------------------------------------
printpathrecursively(8, a, st)
current node not NULL
push 8 to stack st
stack: 8
current node is not leaf node
call to printpathrecursively(8->left, a, st)
call to printpathrecursively(8->right, a, st)
---------------------------------------------------

printpathrecursively(8->left, a, st):
=printpathrecursively(5, a, st)
current node not NULL
push 5 to stack st
stack: 8,5
current node is not leaf node
call to printpathrecursively(5->left, a, st)
call to printpathrecursively(5->right, a, st)
---------------------------------------------------

printpathrecursively(5->left, a, st):
=printpathrecursively(9, a, st)
current node not NULL
push 9 to stack st
stack: 8, 5, 9
current node is leaf node
form the number from the stack
generated number is 859
append 859 to list a
call to printpathrecursively(9->left, a, st)
call to printpathrecursively(9->right, a, st)
call to printpathrecursively(9->left, a, st)
---------------------------------------------------

=printpathrecursively(NULL, a, st)
current node NULL
control return to FUNCTION printpathrecursively(9, a, st)

At printpathrecursively(9, a, st)
call to printpathrecursively(9->right, a, st)
---------------------------------------------------

=printpathrecursively(NULL, a, st)
current node NULL
control return to FUNCTION printpathrecursively(9, a, st)
At printpathrecursively(9, a, st)
Control reaches end of the void function
Thus control returns to the callee
function  printpathrecursively(5, a, st)
---------------------------------------------------

printpathrecursively(5->right, a, st):
=printpathrecursively(7, a, st)
current node not NULL
push 7 to stack st
stack: 8, 5, 7
current node is not leaf node

call to printpathrecursively(7->left, a, st)
call to printpathrecursively(7->right, a, st)
This can be carried out until control gets back to main
which called function printpathrecursively(root, a, st)
```

You can do rest by your own to have much more clear idea about how the program is actually working.

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

class Node{ //tree node
public:
int data;
Node *left;
Node *right;
};

void pathsum(Node* root, stack<int> a,vector<long long int> &digits){
//stack st same as stack a in code
//vector<int> digits in code same as list a
if(!root)
return;
a.push(root->data);
if(!root->left && !root->right){
//code to form numbers from the stack
long long int num=0;
int p=1;
stack<int> a1=a;
while(!a1.empty()){
num+=p*a1.top();
a1.pop();
p*=10;

}
digits.push_back(num); //append number to list
}

pathsum(root->left,a,digits);
pathsum(root->right,a,digits);

}

long long treePathsSum(Node *root)
{
//Your code here
stack<int> a;
vector<long long int> digits;
pathsum(root,a,digits);

long long int sum=0;
for(int i=0;i<digits.size();i++)
sum+=digits[i];

return sum;
}
Node* newnode(int data){  //creating new nodes
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}

int main() {
//**same tree is builted as shown in example**
cout<<"tree in the example is build here"<<endl;
//building the tree like as in the example
Node *root=newnode(8);
root->left= newnode(5);
root->right= newnode(4);
root->right->right=newnode(1);
root->right->right->left=newnode(3);
root->left->left=newnode(9);
root->left->right=newnode(7);
root->left->right->left=newnode(1);
root->left->right->right=newnode(2);
root->left->right->right->left=newnode(2);

cout<<"all root to leaf path sum is......"<<endl;
treePathsSum(root);
return 0;
}
```

Output

```tree in the example is build here
all root to leaf path sum is......
103565
```

TOP Interview Coding Problems/Challenges

Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.