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
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
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:
You can do rest by your own to have much more clear idea about how the program is actually working.
C++ Implementation:
Output
need an explanation for this answer? contact us directly to get an explanation for this answer