Scale Engineer

Sum Root to Leaf Numbers

Med
#0129Time: O(N*H)Space: O(N*H)2 companies
Algorithms
Depth-First Search
Data structures
TreeBinary Tree
Companies
ServiceNowVisa

Prompt

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

  • For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

 

Example 1:

1->2

Example 2:

4->9->5

 

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 9
  • The depth of the tree will not exceed 10.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach first generates all root-to-leaf paths, stores them, and then iterates through these paths to calculate the corresponding numbers and their sum. It's straightforward but inefficient due to high space usage.

Algorithm

  1. Initialize an empty list, allPaths, to store string representations of the numbers for each root-to-leaf path.
  2. Define a recursive helper function findPaths(node, currentPathString, allPaths).
  3. In the helper function, if the current node is null, return.
  4. Append the current node's value to currentPathString.
  5. If the current node is a leaf (both left and right children are null), add the currentPathString to the allPaths list.
  6. Recursively call the helper function for the left and right children.
  7. After the initial call to findPaths on the root completes, iterate through allPaths.
  8. For each string in allPaths, convert it to an integer and add it to a totalSum.
  9. Return totalSum.

Walkthrough

The core idea is to separate the problem into two distinct steps: path finding and summation.

  1. Path Finding: A Depth-First Search (DFS) traversal is used to find all paths from the root to every leaf node. We use a helper function that maintains the current path from the root. When a leaf is encountered, the current path is complete and is added to a list of all paths.

  2. Summation: After the traversal is complete, we have a list of all paths (where each path is a list of digits). We iterate through this list. For each path, we convert the sequence of digits into an integer. For example, the path [4, 9, 5] is converted to the number 495. These numbers are then added to a running total.

Here is a code snippet illustrating this approach:

import java.util.ArrayList;import java.util.List; class Solution {    public int sumNumbers(TreeNode root) {        List<String> allPaths = new ArrayList<>();        findPaths(root, "", allPaths);                int totalSum = 0;        for (String path : allPaths) {            totalSum += Integer.parseInt(path);        }        return totalSum;    }        private void findPaths(TreeNode node, String currentPath, List<String> allPaths) {        if (node == null) {            return;        }                currentPath += node.val;                if (node.left == null && node.right == null) {            allPaths.add(currentPath);            return;        }                findPaths(node.left, currentPath, allPaths);        findPaths(node.right, currentPath, allPaths);    }}

Complexity

Time

O(N*H)

Space

O(N*H)

Trade-offs

Pros

  • The logic is separated into two clear, understandable steps: finding paths and then summing them.

  • It's a direct translation of the problem statement.

Cons

  • Very inefficient in terms of space. It requires storing all root-to-leaf paths, which can be memory-intensive for large trees.

  • The time complexity is also suboptimal due to the overhead of creating and storing path strings/lists and then iterating over them again.

Solutions

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int sumNumbers ( TreeNode root ) { return dfs ( root , 0 ); } private int dfs ( TreeNode root , int s ) { if ( root == null ) { return 0 ; } s = s * 10 + root . val ; if ( root . left == null && root . right == null ) { return s ; } return dfs ( root . left , s ) + dfs ( root . right , s ); } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem