129. Sum Root to Leaf Numbers
Model: qwen3.5:9b
Topics: Tree,Depth-first Search
FAANG asked: 1
Acceptance rate: 51.3%
Problem Breakdown
We are given the root of a binary tree where every node contains a single digit (0-9). The core task is to treat each path from the root down to any leaf as a decimal number and sum them all up.
For example, if we have 1 -> 2, that represents the integer 12. If there’s another branch 1 -> 3, it represents 13. We need to return .
Key Inputs: A binary tree root node (TreeNode).
Output: An integer representing the total sum of all valid paths.
Implicit Constraints & Edge Cases:
- Leaf Definition: Only nodes with no children count as leaves for a path termination. If a node has only one child, it is not a leaf; we must continue down that branch.
- Empty Tree: The constraints state the number of nodes is at least 1, so
rootwill never be null initially. However, our recursion logic should handle children being null gracefully. - Overflow: With depth up to 10 and digits 9-9, a path could represent . In languages like Java or C++, this exceeds the standard signed 32-bit integer limit (), requiring
long. Python handles large integers automatically, so we don’t need to worry about overflow here.
Intuition
A brute-force approach would be to traverse every path from root to leaf, store the number formed by each path in a list or string buffer, and then convert them all to integers at the end for summation. While this works logically, it is inefficient because we are storing intermediate states unnecessarily. We can optimize space significantly if we carry the “current number” down with us as we traverse.
The key insight here is that when moving from a parent node to a child node in a decimal system:
- The current accumulated value needs its digits shifted left (multiplied by 10).
- We add the new digit (
node.val).
So, if current_sum at the root is , and we move to a child with value , the new sum becomes .
This suggests a Depth-First Search (DFS). As we recurse down:
- If we hit a leaf node, the current accumulated
current_sumis our contribution. We return it immediately. - If we are at an internal node, we update the sum and recursively call for left and right children. The total result is the sum of what comes back from both subtrees (if they exist).
Approach
We will use a recursive DFS helper function that takes two arguments:
node: The current tree node being visited.current_sum: An integer representing the number formed by the path so far.
Algorithm Steps:
- Base Case (Leaf): If
nodeis null, return 0. However, strictly speaking for a leaf check: if both left and right children are missing, we treat this node as contributing its current accumulated value to the total sum. - Recursive Step: Update
current_sum: - Accumulate Results: If a left child exists, add the result of recursing on it to our total. Do the same for the right child if it exists.
- Return Total: Return
left_result + right_result.
Note: To keep code clean and avoid checking “is leaf” explicitly inside every call (which can be messy), we handle null nodes by returning 0, but ensure that when a node is truly a leaf (both children are None), the recursion returns its value. Actually, simpler logic: If node has no left child AND no right child, return current_sum. Otherwise recurse on existing children and sum their results.
Complexity Analysis
- Time Complexity: where is the number of nodes in the tree. We visit every node exactly once to calculate its contribution or pass it down.
- Space Complexity: , where is the height of the tree. This accounts for the recursion stack space used during DFS traversal. In a balanced tree this is ; in a skewed (linked-list-like) tree, it degrades to . Given constraints state depth , stack overflow is not a concern here.
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sumNumbers(root: 'TreeNode') -> int:
"""
Calculates the sum of all root-to-leaf numbers.
Args:
root (TreeNode): The root node of the binary tree containing digits 0-9.
Returns:
int: Sum of all paths from root to leaf interpreted as decimal integers.
"""
def dfs(node, current_sum):
# If we reach a null child, it contributes nothing to this path sum
if not node:
return 0
# Update the running number for this level
new_current = (current_sum * 10) + node.val
# Check if leaf node (no children left or right)
if not node.left and not node.right:
return new_current
# Recurse on existing children, summing their results.
# If a child is None, dfs returns 0 immediately above, so this works safely.
total = dfs(node.left, new_current) + dfs(node.right, new_current)
return total
if not root:
return 0
return dfs(root, 0)
Edge Cases Handled
- Single Node Tree: If the tree has only one node (root is a leaf),
dfsupdates sum tonode.val, checks for children (none found), and returns that value. Correctly sums as just that digit. - Null Children in Recursion: The helper function handles null nodes by returning 0 immediately, preventing index errors or attribute access on None objects during the recursive step (
dfs(node.left...)). - Zero Values: Nodes with
val = 0are handled correctly (e.g., path1 -> 0 -> 5becomes , then ). - Deep Trees: While recursion depth is limited by system stack, the problem constraints explicitly limit tree height to 10. Even without that constraint, Python’s default recursion limit (usually 1000) covers .