Sum Root to Leaf Numbers

How to Solve Sum Root to Leaf Numbers

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