{x}
blog image

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.

 

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.

 

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.

129. Sum Root to Leaf Numbers

Problem Description

Given a binary tree where each node contains a digit from 0 to 9, each root-to-leaf path represents a number. Find the total sum of all root-to-leaf numbers. A leaf node is a node with no children.

Solution: Depth-First Search (DFS)

The most efficient approach is using Depth-First Search (DFS). We traverse the tree recursively, building up the number represented by each path as we go.

Algorithm:

  1. Base Case: If the current node is null, return 0 (no contribution to the sum).
  2. Path Number Update: Append the current node's value to the current path number (multiplying the existing number by 10 and adding the current node's value).
  3. Leaf Node Check: If the current node is a leaf node (no left or right children), this path is complete. Add the current path number to the total sum.
  4. Recursive Calls: Recursively call the function on the left and right subtrees, adding their results to the total sum for this branch.

Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.

Space Complexity: O(H), where H is the height of the tree. This accounts for the recursive call stack. In the worst case (a skewed tree), H could be N, but in a balanced tree, H is log₂N.

Code Implementation

Here's the implementation in several programming languages:

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
 
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node, current_sum):
            if not node:
                return 0
            current_sum = current_sum * 10 + node.val
            if not node.left and not node.right:  # Leaf node
                return current_sum
            return dfs(node.left, current_sum) + dfs(node.right, current_sum)
 
        return dfs(root, 0)

Java:

/**
 * 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) { // Leaf node
            return currentSum;
        }
        return dfs(node.left, currentSum) + dfs(node.right, currentSum);
    }
}

C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
 
    int dfs(TreeNode* node, int currentSum) {
        if (!node) return 0;
        currentSum = currentSum * 10 + node->val;
        if (!node->left && !node->right) return currentSum; //Leaf Node
        return dfs(node->left, currentSum) + dfs(node->right, currentSum);
    }
};

//Other languages (Go, TypeScript, Rust, Javascript, C) are omitted for brevity, but follow the same fundamental recursive DFS pattern. The core logic remains consistent across all languages.