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.

AnswerBot
4d

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

Help your peers!
Add answer anonymously...
Josh Technology Group Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter