LeetCode 129: Sum Root to Leaf Numbers Solution in Python – A Step-by-Step Guide

What Is LeetCode 129: Sum Root to Leaf Numbers?

In LeetCode 129: Sum Root to Leaf Numbers, you’re given the root of a binary tree where each node contains a digit (0-9). Your task is to calculate the sum of all numbers formed by traversing from the root to each leaf, where each path represents a number by concatenating the digits along it. For example, with root = [4, 9, 0, 5, 1], the paths are 495, 491, and 40, summing to 1026.

Problem Statement

• Input: Root of a binary tree (TreeNode).
• Output: An integer—the sum of all root-to-leaf path numbers.
• Rules:
• Each node value is a single digit (0-9).
• A path number is formed by concatenating digits from root to leaf.
• Sum all such numbers.

Constraints

• Number of nodes: 1 <= n <= 10⁴
• 0 <= Node.val <= 9
• Tree height ≤ 10

Examples

• Input: root = [1, 2, 3]
• Output: 25
• Why: Paths 1→2 (12) and 1→3 (13), sum = 12 + 13 = 25.
• Input: root = [4, 9, 0, 5, 1]
• Output: 1026
• Why: Paths 4→9→5 (495), 4→9→1 (491), 4→0 (40), sum = 495 + 491 + 40 = 1026.
• Input: root = [0]
• Output: 0
• Why: Single node path is 0.

Understanding the Problem: Summing the Paths

To solve LeetCode 129: Sum Root to Leaf Numbers in Python, we need to traverse the binary tree, form numbers from root-to-leaf paths, and sum them. A naive approach might involve collecting all paths as strings, converting them to integers, and summing—possible, but we can optimize by building numbers during traversal. We’ll explore:

• Best Solution (Recursive DFS): O(n) time, O(h) space—builds numbers on the fly.
• Alternative Solution (Iterative DFS): O(n) time, O(h) space—uses a stack.

Let’s dive into the Best Solution—recursive DFS—and break it down step-by-step.

Best Solution: Recursive DFS with Path Tracking

Why This Is the Best Solution

The recursive DFS approach is the top pick because it’s both efficient—O(n) time, O(h) space (h is tree height)—and intuitive, naturally following the tree’s structure. It builds each path’s number as it traverses, summing at the leaves, all without extra data structures beyond the recursion stack. It’s like walking each path, jotting down digits as you go, and adding up the totals—clean and fast!

How It Works

Here’s the strategy:

• Step 1: Define Helper Function:
• dfs(node, current_num): Tracks the number formed so far.
• Step 2: Base Cases:
• If node is None, return 0 (no path).
• If node is a leaf (no children), return current_num.
• Step 3: Build Number:
• Update current_num = current_num * 10 + node.val.
• Recurse on left and right children, summing their results.
• Step 4: Start Recursion:
• Call dfs(root, 0) from root.

Step-by-Step Example

Example: root = [4, 9, 0, 5, 1]

• Tree:

4 / \ 9 0 / \ 5 1

• dfs(4, 0):
• current_num = 0 * 10 + 4 = 4.
• Left: dfs(9, 4).
• Right: dfs(0, 4).
• dfs(9, 4):
• current_num = 4 * 10 + 9 = 49.
• Left: dfs(5, 49).
• Right: dfs(1, 49).
• dfs(5, 49):
• current_num = 49 * 10 + 5 = 495.
• Leaf, return 495.
• dfs(1, 49):
• current_num = 49 * 10 + 1 = 491.
• Leaf, return 491.
• dfs(9, 4):
• Sum = 495 + 491 = 986.
• dfs(0, 4):
• current_num = 4 * 10 + 0 = 40.
• Leaf, return 40.
• dfs(4, 0):
• Sum = 986 + 40 = 1026.
• Result: 1026.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node, current_num):
            # Step 2: Base cases
            if not node:
                return 0
            current_num = current_num * 10 + node.val
            if not node.left and not node.right:  # Leaf
                return current_num

            # Step 3: Recurse on children
            return dfs(node.left, current_num) + dfs(node.right, current_num)

        # Step 4: Start recursion
        return dfs(root, 0)

• Line 3-11: Helper function:
• Line 5-6: Return 0 for null node.
• Line 7: Build number by shifting left and adding digit.
• Line 8-9: Return number if leaf.
• Line 11: Sum left and right subtrees.
• Line 14: Kick off from root with 0.
• Time Complexity: O(n)—each node visited once.
• Space Complexity: O(h)—recursion stack, h is height.

This is a path-summing maestro!

Alternative Solution: Iterative DFS with Stack

Why an Alternative Approach?

The iterative DFS with a stack offers a non-recursive option—O(n) time, O(h) space—using a stack to track nodes and their partial numbers. It’s useful for avoiding recursion limits in deep trees and provides a different perspective. It’s like hiking the tree with a backpack, noting each path’s progress—explicit and versatile!

How It Works

• Step 1: Use a stack with (node, num) pairs.
• Step 2: Process nodes, build numbers, sum at leaves.
• Step 3: Return total sum.

Step-by-Step Example

Example: root = [4, 9, 0, 5, 1]

• Initialize: stack = [(4, 0)], total_sum = 0.
• (4, 0):
• num = 0 * 10 + 4 = 4.
• Push (9, 4), (0, 4).
• (9, 4):
• num = 4 * 10 + 9 = 49.
• Push (5, 49), (1, 49).
• (5, 49):
• num = 49 * 10 + 5 = 495.
• Leaf, total_sum = 495.
• (1, 49):
• num = 49 * 10 + 1 = 491.
• Leaf, total_sum = 495 + 491 = 986.
• (0, 4):
• num = 4 * 10 + 0 = 40.
• Leaf, total_sum = 986 + 40 = 1026.
• Result: 1026.

Code for Iterative Approach

Copy codeclass Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        stack = [(root, 0)]
        total_sum = 0

        while stack:
            node, current_num = stack.pop()
            current_num = current_num * 10 + node.val

            if not node.left and not node.right:  # Leaf
                total_sum += current_num
            else:
                if node.right:
                    stack.append((node.right, current_num))
                if node.left:
                    stack.append((node.left, current_num))

        return total_sum

• Line 4-5: Handle empty tree.
• Line 7-8: Initialize stack and sum.
• Line 10-19: Stack loop:
• Line 12: Build number.
• Line 14-15: Add to sum if leaf.
• Line 17-19: Push children.
• Time Complexity: O(n)—each node processed once.
• Space Complexity: O(h)—stack size.

It’s a stack-driven number cruncher!

Comparing the Two Solutions

• Recursive DFS (Best):
• Pros: O(n) time, O(h) space, concise and natural.
• Cons: Relies on recursion stack.
• Iterative DFS (Alternative):
• Pros: O(n) time, O(h) space, avoids recursion.
• Cons: More verbose.

Recursive wins for elegance.

Additional Examples and Edge Cases

• [1]: 1.
• [1, 0]: 10.
• [0, 0, 0]: 0 (single path).

Both handle these perfectly.

Complexity Breakdown

• Recursive: Time O(n), Space O(h).
• Iterative: Time O(n), Space O(h).

Recursive’s simplicity shines.

Key Takeaways

• Recursive: Build and sum naturally!
• Iterative: Stack tracks paths!
• Paths: Root to leaf matters.
• Python Tip: Recursion rocks—see [Python Basics](/python/basics).

Final Thoughts: Sum the Branches

LeetCode 129: Sum Root to Leaf Numbers in Python is a tree-traversing treat. The recursive DFS sums paths with grace, while iterative DFS offers a hands-on alternative. Want more tree fun? Try LeetCode 104: Maximum Depth of Binary Tree or LeetCode 124: Binary Tree Maximum Path Sum. Ready to add up? Head to Solve LeetCode 129 on LeetCode and crunch those numbers today!