129. Sum Root to Leaf Numbers - Solution

Q: Is Sum Root to Leaf Numbers easy or hard?

Sum Root to Leaf Numbers is considered a medium-level problem. The tree traversal itself is straightforward, but candidates must recognize how to build numbers incrementally along each path and detect leaf nodes correctly.

Q: Sum Root to Leaf Numbers Python/Java solution

Python and Java solutions both implement DFS. Pass the current path number as a parameter during recursion, update it with current * 10 + node.val, and add it to the result when a leaf is reached. The logic is identical across languages with O(n) time complexity.

Q: How to solve Sum Root to Leaf Numbers in O(n)?

Perform a DFS traversal from the root while maintaining a running number. At each step compute currentNumber = previousNumber * 10 + node.val. When reaching a leaf node, add this number to the total sum. Since the algorithm touches each node once, the total runtime stays O(n).

Q: What is the best approach for Sum Root to Leaf Numbers?

Depth-First Search (DFS) is the best approach. Traverse the binary tree while carrying the number formed so far, updating it as current * 10 + node.val. When a leaf node is reached, add the accumulated value to the total sum. This processes each node once, giving O(n) time complexity.

Q: Is Sum Root to Leaf Numbers asked at Google/Amazon/Meta?

Tree traversal problems similar to Sum Root to Leaf Numbers appear frequently in interviews at companies like Amazon, Google, and Meta. They test understanding of DFS, recursion, and passing state along tree paths. Variations often involve computing values along root-to-leaf paths.

Q: What data structure is used in Sum Root to Leaf Numbers?

The main data structure is a binary tree. The algorithm uses depth-first traversal implemented either through recursion (implicit call stack) or an explicit stack. Both methods track the current numeric value along each path.

Q: What is the time complexity of Sum Root to Leaf Numbers?

The time complexity is O(n) because every node in the binary tree is visited exactly once during the traversal. Each visit performs constant work to update the path number and check whether the node is a leaf. Space complexity is O(h), where h is the height of the tree due to recursion or the DFS stack.

The problem

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.

For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Constraints:

The number of nodes in the tree is in the range [1, 1000].
0 <= Node.val <= 9
The depth of the tree will not exceed 10.

Approach overview

Problem Overview: Each root-to-leaf path in a binary tree forms a number by concatenating node values. For example, the path 1 → 2 → 3 represents 123. The task is to traverse the tree, compute the number formed by every root-to-leaf path, and return the total sum.

Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))

Use a recursive Depth-First Search to explore the tree from the root. Maintain the current number while traversing by multiplying the previous value by 10 and adding the current node's digit. When the traversal reaches a leaf node (both children are null), the accumulated value represents a complete root-to-leaf number, so add it to the total sum.

This approach works naturally with recursion because each call carries the partial number built along the path. The recursion depth equals the tree height, so the extra memory is proportional to O(h), where h is the height of the binary tree. Every node is visited exactly once, producing O(n) time complexity. This is the cleanest and most common solution used in interviews.

Approach 2: Iterative Depth-First Search with Stack (Time: O(n), Space: O(h))

The same traversal can be implemented iteratively using an explicit stack. Store pairs of (node, currentNumber). Start with the root and value root.val. On each iteration, pop a node from the stack, update the number for its children using current * 10 + child.val, and push those children onto the stack.

When a popped node is a leaf, add the computed number to the running sum. The stack simulates the call stack used by recursion. At any time it stores nodes along the current DFS frontier, which keeps the extra memory bounded by the tree height. This method avoids recursion limits and is useful in environments where recursive depth may be constrained.

Recommended for interviews: Recursive DFS is the expected solution. It directly models the idea of building numbers along a path and results in concise code. Interviewers usually want to see that you recognize this as a tree traversal problem and propagate state through the recursion. The iterative stack version demonstrates deeper understanding of DFS mechanics and is helpful when discussing recursion alternatives.

Approach 1: Recursive Depth-First Search (DFS)

This approach makes use of recursive DFS to traverse from the root to all leaf nodes while maintaining the path number formed by the nodes on the path. At each step, multiply the current number by 10 and add the node's value to propagate the root-to-leaf number down the path. When a leaf node is reached, add the path number to an overall sum.

Python

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        def dfs(node, current_sum):
            if not node:
                return 0
            current_sum = current_sum * 10 + node.val
            if not node.left and not node.right:
                return current_sum
            return dfs(node.left, current_sum) + dfs(node.right, current_sum)
        return dfs(root, 0)

Java

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    private int dfs(TreeNode node, int currentSum) {
        if (node == null) return 0;
        currentSum = currentSum * 10 + node.val;
        if (node.left == null && node.right == null) return currentSum;
        return dfs(node.left, currentSum) + dfs(node.right, currentSum);
    }
}

C++

class Solution {
public:
    int dfs(TreeNode* node, int current_sum) {
        if (!node) return 0;
        current_sum = current_sum * 10 + node->val;
        if (!node->left && !node->right) return current_sum;
        return dfs(node->left, current_sum) + dfs(node->right, current_sum);
    }

    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
};

JavaScript

function sumNumbers(root) {
    function dfs(node, currentSum) {
        if (!node) return 0;
        currentSum = currentSum * 10 + node.val;
        if (!node.left && !node.right) return currentSum;
        return dfs(node.left, currentSum) + dfs(node.right, currentSum);
    }
    return dfs(root, 0);
}

#include <stdio.h>

int dfs(struct TreeNode* node, int current_sum) {
    if (node == NULL) return 0;
    current_sum = current_sum * 10 + node->val;
    if (node->left == NULL && node->right == NULL) return current_sum;
    return dfs(node->left, current_sum) + dfs(node->right, current_sum);
}

int sumNumbers(struct TreeNode* root) {
    return dfs(root, 0);
}

public class Solution {
    public int SumNumbers(TreeNode root) {
        return Dfs(root, 0);
    }

    private int Dfs(TreeNode node, int currentSum) {
        if (node == null) return 0;
        currentSum = currentSum * 10 + node.val;
        if (node.left == null && node.right == null) return currentSum;
        return Dfs(node.left, currentSum) + Dfs(node.right, currentSum);
    }
}

The Python solution utilizes the nested function dfs which traverses the binary tree and calculates the path sums for all root-to-leaf paths using a recursive approach.

Complexity

Time Complexity: O(n).
Space Complexity: O(h).

Try this approach in the editor

Approach 2: Iterative Depth-First Search (DFS) with Stack

This approach uses an iterative DFS with a stack to avoid deep recursive calls. Here, we use a stack to simulate the call stack and iterate through the nodes. Each entry in the stack contains the node and the path sum up to that node, allowing us to process nodes on the path to construct the full number.

Python

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        if not root:
            return 0
        stack = [(root, 0)]
        total_sum = 0
        while stack:
            node, current_sum = stack.pop()
            current_sum = current_sum * 10 + node.val
            if not node.left and not node.right:
                total_sum += current_sum
            if node.right:
                stack.append((node.right, current_sum))
            if node.left:
                stack.append((node.left, current_sum))
        return total_sum

Java

import java.util.Stack;

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer> sumStack = new Stack<>();
        nodeStack.push(root);
        sumStack.push(0);

        int total_sum = 0;
        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pop();
            int currentSum = sumStack.pop() * 10 + node.val;

            if (node.left == null && node.right == null) {
                total_sum += currentSum;
            } else {
                if (node.right != null) {
                    nodeStack.push(node.right);
                    sumStack.push(currentSum);
                }
                if (node.left != null) {
                    nodeStack.push(node.left);
                    sumStack.push(currentSum);
                }
            }
        }
        return total_sum;
    }
}

C++

#include <stack>
#include <utility>

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if (!root) return 0;
        std::stack<std::pair<TreeNode*, int>> stk;
        stk.push({root, 0});
        int total_sum = 0;

        while (!stk.empty()) {
            auto [node, current_sum] = stk.top();
            stk.pop();
            current_sum = current_sum * 10 + node->val;

            if (!node->left && !node->right) {
                total_sum += current_sum;
            } else {
                if (node->right) stk.push({node->right, current_sum});
                if (node->left) stk.push({node->left, current_sum});
            }
        }

        return total_sum;
    }
};

JavaScript

function sumNumbers(root) {
    if (!root) return 0;
    let stack = [{node: root, currentSum: 0}];
    let totalSum = 0;

    while (stack.length > 0) {
        let {node, currentSum} = stack.pop();
        currentSum = currentSum * 10 + node.val;

        if (!node.left && !node.right) {
            totalSum += currentSum;
        }
        if (node.right) {
            stack.push({node: node.right, currentSum});
        }
        if (node.left) {
            stack.push({node: node.left, currentSum});
        }
    }

    return totalSum;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    struct TreeNode* node;
    int current_sum;
} StackElement;

typedef struct {
    StackElement* elements;
    int capacity;
    int top;
} Stack;

void initStack(Stack* stack, int capacity) {
    stack->elements = (StackElement*)malloc(capacity * sizeof(StackElement));
    stack->capacity = capacity;
    stack->top = -1;
}

bool isEmpty(Stack* stack) {
    return stack->top == -1;
}

void push(Stack* stack, StackElement element) {
    stack->elements[++stack->top] = element;
}

StackElement pop(Stack* stack) {
    return stack->elements[stack->top--];
}

int sumNumbers(struct TreeNode* root) {
    if (root == NULL) return 0;
    Stack stack;
    initStack(&stack, 1000); // Allocate based on problem constraints
    int total_sum = 0;
    push(&stack, (StackElement){root, 0});

    while (!isEmpty(&stack)) {
        StackElement current = pop(&stack);
        struct TreeNode* node = current.node;
        int current_sum = current.current_sum * 10 + node->val;

        if (node->left == NULL && node->right == NULL) {
            total_sum += current_sum;
        } else {
            if (node->right != NULL) {
                push(&stack, (StackElement){node->right, current_sum});
            }
            if (node->left != NULL) {
                push(&stack, (StackElement){node->left, current_sum});
            }
        }
    }
    free(stack.elements);
    return total_sum;
}

public class Solution {
    public int SumNumbers(TreeNode root) {
        if (root == null) return 0;
        Stack<Tuple<TreeNode, int>> stack = new Stack<Tuple<TreeNode, int>>();
        stack.Push(Tuple.Create(root, 0));
        int total_sum = 0;

        while (stack.Count > 0) {
            var current = stack.Pop();
            TreeNode node = current.Item1;
            int currentSum = current.Item2 * 10 + node.val;

            if (node.left == null && node.right == null) {
                total_sum += currentSum;
            }
            if (node.right != null) {
                stack.Push(Tuple.Create(node.right, currentSum));
            }
            if (node.left != null) {
                stack.Push(Tuple.Create(node.left, currentSum));
            }
        }

        return total_sum;
    }
}

Python utilizes a list to implement the stack for iterating over nodes. Each tuple in the stack maintains the node and the path sum up to that point.

Complexity

Time Complexity: O(n).
Space Complexity: O(n).

Try this approach in the editor

Approach 3: DFS

We can design a function dfs(root, s), which represents the sum of all path numbers from the current node root to the leaf nodes, given that the current path number is s. The answer is dfs(root, 0).

The calculation of the function dfs(root, s) is as follows:

If the current node root is null, return 0.
Otherwise, add the value of the current node to s, i.e., s = s times 10 + root.val.
If the current node is a leaf node, return s.
Otherwise, return dfs(root.left, s) + dfs(root.right, s).

The time complexity is O(n), and the space complexity is O(log n). Here, n is the number of nodes in the binary tree.

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function sumNumbers(root: TreeNode | null): number {
    function dfs(root: TreeNode | null, s: number): number {
        if (!root) return 0;
        s = s * 10 + root.val;
        if (!root.left && !root.right) return s;
        return dfs(root.left, s) + dfs(root.right, s);
    }
    return dfs(root, 0);
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
	var dfs func(*TreeNode, int) int
	dfs = func(root *TreeNode, s int) int {
		if root == nil {
			return 0
		}
		s = s*10 + root.Val
		if root.Left == nil && root.Right == nil {
			return s
		}
		return dfs(root.Left, s) + dfs(root.Right, s)
	}
	return dfs(root, 0)
}

Rust

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, mut num: i32) -> i32 {
        if node.is_none() {
            return 0;
        }
        let node = node.as_ref().unwrap().borrow();
        num = num * 10 + node.val;
        if node.left.is_none() && node.right.is_none() {
            return num;
        }
        Self::dfs(&node.left, num) + Self::dfs(&node.right, num)
    }

    pub fn sum_numbers(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        Self::dfs(&root, 0)
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Depth-First Search (DFS)	Time Complexity: O(n). Space Complexity: O(h).
Iterative Depth-First Search (DFS) with Stack	Time Complexity: O(n). Space Complexity: O(n).
DFS	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive DFS	O(n)	O(h)	Default interview solution for binary tree traversal problems
Iterative DFS with Stack	O(n)	O(h)	When avoiding recursion limits or implementing DFS manually

Frequently asked questions

Is Sum Root to Leaf Numbers easy or hard?

Sum Root to Leaf Numbers is considered a medium-level problem. The tree traversal itself is straightforward, but candidates must recognize how to build numbers incrementally along each path and detect leaf nodes correctly.

Sum Root to Leaf Numbers Python/Java solution

Python and Java solutions both implement DFS. Pass the current path number as a parameter during recursion, update it with current * 10 + node.val, and add it to the result when a leaf is reached. The logic is identical across languages with O(n) time complexity.

How to solve Sum Root to Leaf Numbers in O(n)?

Perform a DFS traversal from the root while maintaining a running number. At each step compute currentNumber = previousNumber * 10 + node.val. When reaching a leaf node, add this number to the total sum. Since the algorithm touches each node once, the total runtime stays O(n).

What is the best approach for Sum Root to Leaf Numbers?

Depth-First Search (DFS) is the best approach. Traverse the binary tree while carrying the number formed so far, updating it as current * 10 + node.val. When a leaf node is reached, add the accumulated value to the total sum. This processes each node once, giving O(n) time complexity.

Is Sum Root to Leaf Numbers asked at Google/Amazon/Meta?

Tree traversal problems similar to Sum Root to Leaf Numbers appear frequently in interviews at companies like Amazon, Google, and Meta. They test understanding of DFS, recursion, and passing state along tree paths. Variations often involve computing values along root-to-leaf paths.

What data structure is used in Sum Root to Leaf Numbers?

The main data structure is a binary tree. The algorithm uses depth-first traversal implemented either through recursion (implicit call stack) or an explicit stack. Both methods track the current numeric value along each path.

What is the time complexity of Sum Root to Leaf Numbers?

The time complexity is O(n) because every node in the binary tree is visited exactly once during the traversal. Each visit performs constant work to update the path number and check whether the node is a leaf. Space complexity is O(h), where h is the height of the tree due to recursion or the DFS stack.

Sum Root to Leaf Numbers solution and explanation

The problem

Approach overview

Approach 1: Recursive Depth-First Search (DFS)

Approach 2: Iterative Depth-First Search (DFS) with Stack

Approach 3: DFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Sum Root to Leaf Numbers solution and explanation

The problem

Approach overview

Approach 1: Recursive Depth-First Search (DFS)

Approach 2: Iterative Depth-First Search (DFS) with Stack

Approach 3: DFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems