Sum Root to Leaf Numbers

Traverse a binary tree and sum all numbers formed by root-to-leaf paths.

binary-tree dfs recursion path-sum

Define a class `TreeNode` with attributes `val`, `left`, and `right`. Implement the function `sum_root_to_leaf(root)` that takes the root of a binary tree (or `None`) and returns the sum of all numbers formed by reading the values along each root-to-leaf path. A root-to-leaf path is a path from the root to any node with no children. The number for a path is formed by concatenating the node values in order. Return 0 if the tree is empty.

Define the function signature exactly as: `def sum_root_to_leaf(root: TreeNode) -> int:`

Constraints

The number of nodes in the tree is between 0 and 1000. Each node's value is between 0 and 9. The sum may exceed 32-bit integers; return it as a Python int.

Example

>>> root = TreeNode(1)
>>> root.left = TreeNode(2)
>>> root.right = TreeNode(3)
>>> sum_root_to_leaf(root)
25
>>> root = TreeNode(4)
>>> root.left = TreeNode(9)
>>> root.right = TreeNode(0)
>>> root.left.left = TreeNode(5)
>>> root.left.right = TreeNode(1)
>>> sum_root_to_leaf(root)
1026
>>> sum_root_to_leaf(None)
0

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a depth-first search that carries the current path number as a parameter.

When reaching a leaf (no children), add the current path number to a total.

If root is None, the total is 0.

Recursively compute the sum for left and right subtrees and add them.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.