# LeetCode 129: Sum Root to Leaf Numbers ## Problem Restatement We are given the root of a binary tree. Each node contains a digit from `0` to `9`. Every root-to-leaf path represents one number. For example, the path `1 -> 2 -> 3` represents the number `123`. We need to return the sum of all numbers formed by all root-to-leaf paths. A leaf is a node with no children. The answer is guaranteed to fit in a 32-bit integer. ## Examples Example 1: ```text 1 / \ 2 3 ``` There are two root-to-leaf paths: ```text 1 -> 2 represents 12 1 -> 3 represents 13 ``` So the answer is: ```python 12 + 13 = 25 ``` Output: ```python 25 ``` Example 2: ```text 4 / \ 9 0 / \ 5 1 ``` The root-to-leaf paths are: ```text 4 -> 9 -> 5 represents 495 4 -> 9 -> 1 represents 491 4 -> 0 represents 40 ``` So the answer is: ```python 495 + 491 + 40 = 1026 ``` Output: ```python 1026 ``` ## Input and Output | Item | Meaning | |---|---| | Input | `root: Optional[TreeNode]` | | Output | Sum of all root-to-leaf numbers | | Node value | A digit from `0` to `9` | | Leaf | A node with no left child and no right child | Function shape: ```python class Solution: def sumNumbers(self, root: Optional[TreeNode]) -> int: ... ``` ## Core Idea As we walk down a path, we build the current number digit by digit. Suppose the current path is: ```text 1 -> 2 -> 3 ``` We build the number like this: ```text start = 0 after 1: 0 * 10 + 1 = 1 after 2: 1 * 10 + 2 = 12 after 3: 12 * 10 + 3 = 123 ``` So when we visit a node, the update rule is: ```python current = current * 10 + node.val ``` This works because multiplying by `10` shifts the previous digits one decimal place to the left, then `node.val` becomes the new last digit. ## Why DFS Fits A root-to-leaf number depends on the full path from the root to one leaf. Depth-first search naturally follows one full path before returning to explore another path. At each node, DFS carries the number formed so far. When DFS reaches a leaf, the current number is complete, so we return it. Then parent calls add the sums from their left and right subtrees. ## Algorithm Use a recursive helper: ```python dfs(node, current) ``` where: | Name | Meaning | |---|---| | `node` | Current tree node | | `current` | Number formed before adding `node.val` | For each call: 1. If `node` is `None`, return `0`. 2. Update `current = current * 10 + node.val`. 3. If `node` is a leaf, return `current`. 4. Recursively compute the left subtree sum. 5. Recursively compute the right subtree sum. 6. Return `left_sum + right_sum`. ## Correctness At every node, `current` equals the number formed by the path from the root to that node. This is true at the root because we start with `0`, then append the root digit. If it is true for a parent, then for a child the update: ```python current * 10 + child.val ``` correctly appends the child digit to the parent path number. When the DFS reaches a leaf, the path cannot continue. Therefore, the current value is exactly one complete root-to-leaf number. The recursion returns that number for each leaf and adds the results from all subtrees. Since every root-to-leaf path ends at exactly one leaf, every valid number is counted once. Therefore, the algorithm returns the total sum of all root-to-leaf numbers. ## Complexity Let `n` be the number of nodes in the tree, and let `h` be the height of the tree. | Metric | Value | Why | |---|---:|---| | Time | `O(n)` | Each node is visited once | | Space | `O(h)` | Recursion stack follows one root-to-leaf path | In the worst case, a skewed tree has height `n`, so the space can be `O(n)`. In a balanced tree, the height is `O(log n)`. ## Implementation ```python from typing import Optional # 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: Optional[TreeNode], current: int) -> int: if node is None: return 0 current = current * 10 + node.val if node.left is None and node.right is None: return current return dfs(node.left, current) + dfs(node.right, current) return dfs(root, 0) ``` ## Code Explanation The helper receives the current node and the number formed before this node: ```python def dfs(node: Optional[TreeNode], current: int) -> int: ``` If the node is missing, it contributes nothing: ```python if node is None: return 0 ``` Then we append the current digit: ```python current = current * 10 + node.val ``` If this node is a leaf, the number is complete: ```python if node.left is None and node.right is None: return current ``` Otherwise, the answer from this subtree is the sum of the answers from its children: ```python return dfs(node.left, current) + dfs(node.right, current) ``` The main function starts with no digits accumulated: ```python return dfs(root, 0) ``` ## Testing ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def run_tests(): s = Solution() root = TreeNode(1, TreeNode(2), TreeNode(3)) assert s.sumNumbers(root) == 25 root = TreeNode( 4, TreeNode(9, TreeNode(5), TreeNode(1)), TreeNode(0), ) assert s.sumNumbers(root) == 1026 root = TreeNode(7) assert s.sumNumbers(root) == 7 root = TreeNode(0, TreeNode(1), TreeNode(2)) assert s.sumNumbers(root) == 3 root = TreeNode(1, None, TreeNode(2, None, TreeNode(3))) assert s.sumNumbers(root) == 123 print("all tests passed") run_tests() ``` Test meaning: | Test | Why | |---|---| | `1` with children `2` and `3` | Basic two-path case | | `4,9,0,5,1` tree | Standard multi-level case | | Single node | A root can also be a leaf | | Root value `0` | Leading zero should still build valid numbers | | Skewed tree | Confirms recursion works down one branch |