Sum Root to Leaf Numbers

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.

For example, given the binary tree [1,2,3], the output should be 25 because the path 1->2 represents 12 and 1->3 represents 13, so the sum is 12 + 13 = 25. As another example, given the binary tree [4,9,0,5,1], the output should be 1026 because the path 4->9->5 is 495, 4->9->1 is 491, and 4->0 is 40, so the sum is 495 + 491 + 40 = 1026.

Question: Sum Root to Leaf Numbers

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. 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:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Solution

This problem can be solved using Depth-First Search (DFS). We traverse the tree, keeping track of the current number formed along the path. When we reach a leaf node, we add the current number to the total sum.

Naive Solution

A simple recursive approach would be to traverse the tree and, at each node, update the path number. When a leaf node is encountered, its path number is added to a running total.

/**
 * 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 sumNumbersHelper(root, 0);
    }

    private int sumNumbersHelper(TreeNode node, int currentNumber) {
        if (node == null) {
            return 0;
        }

        currentNumber = currentNumber * 10 + node.val;

        if (node.left == null && node.right == null) {
            return currentNumber;
        }

        return sumNumbersHelper(node.left, currentNumber) + sumNumbersHelper(node.right, currentNumber);
    }
}

Optimal Solution

The provided solution is already quite optimal for the constraints given. The logic remains unchanged, but the code can be refactored for better readability.

/**
 * 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 node, int currentSum) {
        if (node == null) {
            return 0;
        }

        currentSum = currentSum * 10 + node.val;

        if (node.left == null && node.right == null) {
            return currentSum;
        }

        return dfs(node.left, currentSum) + dfs(node.right, currentSum);
    }
}

Big(O) Run-time Analysis

The time complexity is O(N), where N is the number of nodes in the binary tree. This is because we visit each node exactly once during the depth-first traversal.

Big(O) Space Usage Analysis

The space complexity is O(H), where H is the height of the binary tree. This is due to the call stack during the recursive DFS traversal. In the worst-case scenario (skewed tree), H can be equal to N, making the space complexity O(N). In the best-case scenario (balanced tree), H would be log(N), making the space complexity O(log(N)).

Edge Cases

1. Empty Tree: If the root is null, the function should return 0.
2. Single Node Tree: If the tree contains only the root node, the function should return the value of the root node.
3. Large Numbers: The problem statement guarantees that the answer fits within a 32-bit integer, so no special handling is needed for overflow.
4. Nodes with Value 0: The algorithm should correctly handle nodes with a value of 0.