MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Solve Sum Root to Leaf Numbers

Written By ## Sum Root to Leaf Numbers Introduction

The Sum Root to Leaf Numbers problem asks us to return the total sum of all root-to-leaf numbers. This problem requires us to traverse the tree using depth-first search and keep track of the current sum, adding the number from each leaf node we come across.

## Sum Root to Leaf Numbers Problem

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.

### Example Inputs and Outputs

#### Example 1

Input: Input: root = [1,2,3]
Output: 25

#### Example 2

Input: root = [4,9,0,5,1]
Output: 1026

## Sum Root to Leaf Numbers Solutions

To solve this problem, we can use a depth-first search (DFS) approach to traverse the binary tree. We can keep track of the current sum, which represents the number that is formed by the path from the root to the current node. If we get to a leaf node, we add the current sum to the total sum. Otherwise, we can recursively traverse the left and right subtrees, updating the current sum along the way. Finally, we return the total sum as the result.

``````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):
def dfs(node, currSum):
if not node:
return 0

# Calculate the current number by appending the node's value to the current sum
currSum = currSum * 10 + node.val

# If it's a leaf node, return the current number
if not node.left and not node.right:
return currSum

# Recursively traverse the left and right subtrees, passing the updated current number
leftSum = dfs(node.left, currSum)
rightSum = dfs(node.right, currSum)

# Return the sum of both left and right subtree sums
return leftSum + rightSum

return dfs(root, 0)

# Create the binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# Call the sumNumbers function and print the result
solution = Solution()
result = solution.sumNumbers(root)
print("Sum of numbers in the binary tree:", result)``````

#### Time/Space Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the binary tree. We visit each node exactly once during the depth-first search traversal.
• Space Complexity: O(H), where H is the height of the binary tree. In the worst case, the recursion stack can grow up to the height of the tree.