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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum Root to Leaf Numbers

Difficulty: Medium

Problem Description

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. Return the total sum of all root-to-leaf numbers. A leaf node is a node with no children.

Key Insights

  • Each root-to-leaf path can be interpreted as a number formed by concatenating the values of the nodes along the path.
  • A depth-first search (DFS) approach is suitable for traversing the tree and calculating the sum of numbers formed by root-to-leaf paths.
  • We need to handle the concatenation of digits correctly by maintaining the current number as we traverse down the tree.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as we visit each node once. Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.

Solution

The solution uses a depth-first search (DFS) approach to traverse the binary tree. Starting from the root, we maintain a variable that stores the current number formed by the path from the root to the current node. When we reach a leaf node, we add the current number to a cumulative sum. The algorithm recursively calls itself for the left and right children of the current node.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sumNumbers(root: TreeNode) -> int:
    def dfs(node, current_sum):
        if not node:
            return 0
        current_sum = current_sum * 10 + node.val
        # If it's a leaf node, return the current sum
        if not node.left and not node.right:
            return current_sum
        # Recur for left and right children
        return dfs(node.left, current_sum) + dfs(node.right, current_sum)

    return dfs(root, 0)
← Back to All Questions