Skip to main content
Talentd

Sum Root to Leaf Numbers - Solution & Explanation

MediumTreeDepth-First SearchBinary Tree21 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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.

We use a helper function dfs that recursively computes the sum of the current path number while traversing the tree. If a leaf node is reached, it returns the current computed path sum. Otherwise, it recurses deeper into the tree.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes, as it has to visit each node.
Space Complexity: O(h), where h is the height of the tree due to recursive call stack.

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.

This C solution uses a manually managed stack to simulate the DFS traversal. Each element in the stack stores the current node and the sum formed up to that node. The approach emulates the process of recursion iteratively.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(n), due to the stack storing all nodes at least once.

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.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Depth-First Search (DFS)

Time Complexity: O(n), where n is the number of nodes, as it has to visit each node.
Space Complexity: O(h), where h is the height of the tree due to recursive call stack.

Iterative Depth-First Search (DFS) with Stack

Time Complexity: O(n).
Space Complexity: O(n), due to the stack storing all nodes at least once.

DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive DFSO(n)O(h)Default interview solution for binary tree traversal problems
Iterative DFS with StackO(n)O(h)When avoiding recursion limits or implementing DFS manually

Video Solution

Sum Root to Leaf Numbers - Coding Interview Question - Leetcode 129 • NeetCode • 43,596 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Sum Root to Leaf Numbers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Maximum Path Sum

Next

Path Sum