We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum Root to Leaf Numbers

Number: 129

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Microsoft, ServiceNow, Google

Problem Description

Given a binary tree where each node contains a single digit (0-9), every root-to-leaf path forms a number by concatenating the digits along that path. The goal is to calculate the sum of all these numbers.

Key Insights

  • Utilize a Depth-First Search (DFS) or recursion strategy to traverse the tree.
  • Carry forward a running value that represents the number formed from the root to the current node.
  • When a leaf node is reached, the currently formed number is complete and can be added to the total sum.
  • Use the mathematical transformation current_value * 10 + node.val to update the number along the path.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes in the tree. Space Complexity: O(h) where h is the height of the tree because of the recursion call stack.

Solution

The problem can be solved using recursive DFS. Start at the root with an initial value of 0. For each node, update the accumulated number by multiplying the current sum by 10 and adding the node's digit. When a leaf is encountered (a node with no children), add the current number to the total sum. Finally, return the sum of numbers formed from all root-to-leaf paths. This approach guarantees that every node is visited exactly once and uses only the call stack proportional to the height of the tree.

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        # Define a helper function for DFS traversal.
        def dfs(node, current_sum):
            if not node:
                return 0
            # Update the current sum (forming the number by appending current node's value).
            current_sum = current_sum * 10 + node.val
            # If the node is a leaf, return the current sum.
            if not node.left and not node.right:
                return current_sum
            # Recursively compute the sum for left and right subtrees.
            left_sum = dfs(node.left, current_sum)
            right_sum = dfs(node.right, current_sum)
            return left_sum + right_sum

        # Start DFS from the root with an initial sum of 0.
        return dfs(root, 0)
← Back to All Questions