Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 129. Sum Root to Leaf Numbers

Given a binary tree whose nodes are digits 0–9, compute the sum of all integers formed by concatenating digits along each root-to-leaf path (e.g., 1→2→3 represents 123); tree size ≤1000 and depth ≤10.

Asked at:

Meta

DESCRIPTION

Input:

nodes = [1, 2, 3]

Output:

Explanation: The tree has root 1 with left child 2 and right child 3. Path 1→2 forms number 12, path 1→3 forms number 13. Sum is 12 + 13 = 25

Constraints:

The number of nodes in the tree is in the range [1, 1000]
The depth of the tree will not exceed 10
Each node's value is a digit from 0 to 9
All root-to-leaf paths will form valid integers (no overflow concerns given the constraints)

Understanding the Problem

Let's understand what we're being asked to do. We have a binary tree where each node contains a single digit from 0 to 9. We need to find all paths from the root to each leaf, treat the digits along each path as forming a number, and sum all these numbers.

For example, if we have a tree with root 1, left child 2, and right child 3, we have two root-to-leaf paths: 1→2 (forming the number 12) and 1→3 (forming the number 13). The sum would be 12 + 13 = 25.

Let's trace through a more complex example: root 4, left child 9 (with children 5 and 1), right child 0. The paths are: 4→9→5 (number 495), 4→9→1 (number 491), and 4→0 (number 40). The sum is 495 + 491 + 40 = 1026.

Important constraints: Tree size can be up to 1000 nodes, depth up to 10, and each node contains a digit 0-9.

Edge cases to consider: What if the tree has only one node (the root is also a leaf)? What if a path contains leading zeros (like 0→5 forming 05, which is just 5)? What if the tree is skewed (all nodes in a single path)?

Building Intuition

As we traverse from root to leaf, we're building a number digit by digit. If we're at a node with value 5 and the number formed so far is 12, then the new number becomes 12 * 10 + 5 = 125.

This means we can accumulate the number as we go down rather than storing the entire path and converting it at the end.

By building the number incrementally during traversal, we avoid storing paths and doing string-to-number conversions. When we reach a leaf node, we already have the complete number formed by that path.

This transforms the problem from 'collect all paths then process' to 'process as we traverse', which is more efficient in both time and space.

Think about how you read a number left-to-right: when you see '1', you have 1. When you see the next digit '2', you shift the previous number left (multiply by 10) and add the new digit: 1 * 10 + 2 = 12. When you see '3', you do it again: 12 * 10 + 3 = 123.

Tree traversal works the same way! As we go down from parent to child, we're reading digits left-to-right. When we reach a leaf (no more children), we've read the complete number and can add it to our sum.

Common Mistakes

Forgetting to check if a node is a leaf before adding to sum - adding at every node instead of only at leaves will count partial paths incorrectly

Not handling the single-node case where root is also a leaf - this edge case should return the root's value, not 0

Trying to build the number using string concatenation and then parsing - this is less efficient than the mathematical approach of multiplying by 10 and adding digits

Modifying a global variable for the current number instead of passing it as a parameter - this breaks when backtracking because the value isn't properly restored

Confusing pre-order traversal (process node, then children) with post-order (process children, then node) - for this problem, we need to accumulate the number before reaching children, so we process the current node's digit first

Optimal Solution

Use depth-first search (DFS) to traverse the tree from root to leaves. As we traverse down each path, maintain a running number by multiplying the current number by 10 and adding the current node's digit. When we reach a leaf node (no children), add the accumulated number to our total sum. Recursively explore both left and right subtrees, backtracking naturally as the recursion unwinds. This approach visits each node exactly once and processes each path efficiently.

Visualization

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def sum_root_to_leaf(root):
    """
    Compute sum of all root-to-leaf path numbers using DFS.
    Time: O(n), Space: O(h) where h is tree height.
    """
    def dfs(node, current_number):
        # Base case: empty node
        if not node:
            return 0
        
        # Build current path number
        current_number = current_number * 10 + node.val
        
        # Leaf node: return accumulated number
        if not node.left and not node.right:
            return current_number
        
        # Recursively explore left and right subtrees
        left_sum = dfs(node.left, current_number)
        right_sum = dfs(node.right, current_number)
        
        # Return total sum from both subtrees
        return left_sum + right_sum
    
    # Start DFS from root with initial number 0
    return dfs(root, 0)

Start: Compute sum of all root-to-leaf path numbers

0 / 17

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We visit each node in the tree exactly once, where n is the number of nodes. At each node, we perform constant-time operations (multiply by 10, add digit, check if leaf)

Space Complexity: O(h) The space is used by the recursion call stack, which in the worst case (skewed tree) can be O(n), but typically is O(h) where h is the height of the tree. Given the constraint that depth ≤ 10, this is effectively O(10) = O(1) in practice

What We've Learned

DFS path accumulation pattern: When you need to track values along a path from root to leaf in a tree, use DFS with accumulated state passed as a parameter - multiply the current path value by 10 and add the new digit at each level, naturally building the number as you traverse downward.
Leaf node identification: A critical implementation detail is correctly identifying leaf nodes with `if not node.left and not node.right` - only accumulate the final number when reaching a leaf, not at every node, to avoid counting partial paths.
Recursive state passing vs global state: Pass the accumulated path value as a function parameter (e.g., `dfs(node, current_sum * 10 + node.val)`) rather than using global variables - this automatically handles backtracking and keeps each path's calculation independent without manual cleanup.
Base case ordering matters: Always check `if not node: return 0` before checking for leaf nodes - this prevents null pointer errors when recursing on `node.left` or `node.right` that don't exist, and ensures clean termination of recursive branches.
O(n) time with implicit backtracking: This solution achieves O(n) time and O(h) space because each node is visited once, and the call stack depth equals tree height - the accumulated value is passed by value (in most languages), so backtracking happens automatically without extra operations.
Path-to-value aggregation pattern: This technique extends to any problem requiring aggregation of values along tree paths - such as finding max/min path sums, counting paths with specific properties, or building strings from root to leaf - the key is recognizing when you need to accumulate state during traversal and sum results at leaf nodes.

Test Your Understanding

Why is tree the right data structure for this problem?

tree provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early November, 2025

Meta

Mid-level

Early October, 2025

Meta

Mid-level

Early October, 2025

Meta

Senior

Get Premium to View All 10+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 129. Sum Root to Leaf Numbers

DESCRIPTION

Understanding the Problem

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact