algoadvance

The problem requires you to find the sum of all numbers formed from root to leaf paths in a binary tree. Each path from the root to a leaf forms a number by concatenating the values of the nodes. For example, if the path forms the numbers 1 -> 2 -> 3, the number is 123.

Given the root of a binary tree, return the total sum of all root-to-leaf numbers.

Clarifying Questions

1. What constitutes a leaf node?
   • A leaf node is a node with no children.
2. Can the tree contain negative values or only non-negative integers?
   • The tree will only contain non-negative integers as per typical interpretations of this problem.
3. Is the binary tree balanced or can it be any shape?
   • The binary tree can be of any shape. It does not need to be balanced.

Strategy

We will use Depth-First Search (DFS) to traverse the tree. As we traverse, we will maintain the current number formed by the nodes’ path. When we reach a leaf node, we will add this number to the total sum. The DFS approach can be implemented using recursion.

1. Initialize total_sum as 0.
2. Define a recursive function dfs(node, current_number) where node is the current node, and current_number is the number formed from the root to that node.
3. If the node is None, return 0 (this handles the base case for an empty subtree).
4. Update the current_number as current_number * 10 + node.val.
5. If the node is a leaf, add the current_number to total_sum.
6. Recursively call the dfs on the left and right subtrees and accumulate their results.
7. Finally, return total_sum after traversing the entire tree.

Code

# Definition for a binary tree node.
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: TreeNode) -> int:
        def dfs(node, current_number):
            if not node:
                return 0
            current_number = current_number * 10 + node.val
            if not node.left and not node.right:  # It's a leaf
                return current_number
            # Recursive case for left and right children
            left_sum = dfs(node.left, current_number)
            right_sum = dfs(node.right, current_number)
            return left_sum + right_sum
        
        return dfs(root, 0)

Time Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
• Space Complexity: O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case (a skewed tree), the height of the tree can be N, but in the best case of a balanced tree, the height is log(N).

This solution efficiently traverses the tree and accumulates the required sums while handle base cases correctly.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?