Home » Interview coding problems/challenges

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

Explanation with example

    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