How to Solve Sum Root to Leaf Numbers

Written By
Adam Bhula

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.

About is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.