Sum Root to Leaf Numbers

Medium Trees & BST Recursion Original on LeetCode

Reported atSwiggy

Sum Root to Leaf Numbers is a medium trees & bst problem solved with the recursion pattern. The best approach, optimal (dfs carrying the number), runs in O(n) time and O(h) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (collect path strings) up.

Problem

Every node of a binary tree holds a single digit from 0 to 9. Reading the digits along a path from the root down to a leaf spells out a number; for example, the path 5 -> 0 -> 2 stands for 502.

Return the sum of the numbers spelled by all root-to-leaf paths. A leaf is a node with no children.

Examples

Example 1

Input
root = [2, 7, 3, null, 4]
Output
297
Why
The two root-to-leaf paths spell 274 and 23, and 274 + 23 = 297.

Example 2

Input
root = [6, 0, null, 1, 8]
Output
1209
Why
Both leaves hang under the 0, giving 601 and 608. The 0 in the middle still counts as a digit.

Example 3

Input
root = [9]
Output
9
Why
The root is also a leaf, so the only number is 9.

Constraints

  • The tree has between 1 and 1000 nodes.
  • 0 <= Node.val <= 9
  • The depth of the tree is at most 10.
  • The answer fits in a 32-bit signed integer.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (collect path strings)O(n · h)O(n · h)
Optimal (DFS carrying the number)O(n)O(h)

1Brute force (collect path strings)

TimeO(n · h)Building a string copy at each node costs up to h characters; parsing the leaves' strings costs O(h) each.
SpaceO(n · h)Up to n / 2 leaf strings of length up to h, plus the recursion stack.

Walk every root-to-leaf path while building a string of its digits. At each leaf, save the string. Afterwards, parse each string as a number and add them up.

  1. DFS from the root, appending the current digit to a path string.
  2. At a leaf, add the finished string to a list.
  3. Parse every string in the list and sum the values.
class Solution {
    public int sumNumbers(TreeNode root) {
        List<String> paths = new ArrayList<>();
        collect(root, "", paths);
        long total = 0;
        for (String p : paths) total += Long.parseLong(p);
        return (int) total;
    }

    private void collect(TreeNode node, String path, List<String> paths) {
        if (node == null) return;
        String next = path + node.val;
        if (node.left == null && node.right == null) {
            paths.add(next);
            return;
        }
        collect(node.left, next, paths);
        collect(node.right, next, paths);
    }
}

2Optimal (DFS carrying the number)

TimeO(n)Every node is visited once with O(1) work.
SpaceO(h)The recursion stack is as deep as the tree, at most 10 here.

Carry the number built so far down the recursion instead of a string. Appending a digit is cur * 10 + val. A leaf returns its finished number; any other node returns the sum of what its children return. A missing child contributes 0.

  1. dfs(node, cur): if node is null, return 0.
  2. cur = cur * 10 + node.val.
  3. If node is a leaf, return cur.
  4. Otherwise return dfs(node.left, cur) + dfs(node.right, cur).
  5. The answer is dfs(root, 0).
class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, int cur) {
        if (node == null) return 0;
        cur = cur * 10 + node.val;
        if (node.left == null && node.right == null) return cur;
        return dfs(node.left, cur) + dfs(node.right, cur);
    }
}

Edge cases to test

  • A single node: the answer is its own digit
  • Zeros along a path, including a 0 at the root (leading zero)
  • A node with only one child is not a leaf; only the child's side forms a number
  • A skewed tree that is one long path

Hints

Hint 1

Each path builds its number one digit at a time. If the number so far is cur and the next digit is d, what is the new number?

Hint 2

Pass cur * 10 + node.val down the recursion and add it to the total only when you reach a leaf.

FAQ

What is the best time complexity for Sum Root to Leaf Numbers?

Optimal (DFS carrying the number) runs in O(n) time and O(h) extra space. Every node is visited once with O(1) work.

Which pattern does Sum Root to Leaf Numbers use?

It is a trees & bst problem that uses the recursion pattern. Other problems with the same pattern: Binary Tree Inorder Traversal (Recursive), Binary Tree Preorder Traversal (Recursive), Binary Tree Postorder Traversal (Recursive).

Is there a brute force solution for Sum Root to Leaf Numbers?

Yes. Brute force (collect path strings) takes O(n · h) time and O(n · h) space. Walk every root-to-leaf path while building a string of its digits.

Which edge cases should I test for Sum Root to Leaf Numbers?

A single node: the answer is its own digit; Zeros along a path, including a 0 at the root (leading zero); A node with only one child is not a leaf; only the child's side forms a number; A skewed tree that is one long path.