Sum Root to Leaf Path Problem
You are given an arbitrary binary tree consisting of N
nodes where each node is associated with an integer value from 1 to 9. Each root-to-leaf path in the tree represents a number formed by concatenating the values from root to leaf.
Example:
1
/ \
2 3
The root to leaf path 1->2 represents the number 12.
The root to leaf path 1->3 represents the number 13.
Your task is to calculate the total sum of all the possible root-to-leaf paths in the tree.
Input:
1
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output:
25
Constraints:
1 ≤ T ≤ 50
- the number of test cases.1 ≤ N ≤ 3000
- number of nodes in the tree.1 ≤ nodeValue ≤ 9
- node values are between 1 and 9.
Note:
The output may be very large, return the answer modulo (109 + 7)
.
Example Explanation:
The total sum of all the root-to-leaf paths is 12 (from path 1->2) + 13 (from path 1->3) = 25. Hence, the output is 25.
In the input, nodes are represented in level order, using -1 for null nodes.
Calculate the total sum of all possible root-to-leaf paths in a binary tree.
Traverse the tree from root to leaf nodes, keeping track of the current path sum.
Add the path sum to the total sum when reac...read more
Top Josh Technology Group Software Developer Intern interview questions & answers
Popular interview questions of Software Developer Intern
Reviews
Interviews
Salaries
Users/Month