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.

Examples

Example 1:

1
2
3

    1
   / \
  2   3

1
2
3
4
5
6

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:

1
2
3
4
5

    4
   / \
  9   0
 / \
5   1

1
2
3
4
5
6
7

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.

Solution

To solve this problem, we traverse the entire binary tree and compute numbers for each root-to-leaf path. For every node in the tree, the number represented by the path extending down to that node can be calculated by multiplying the sum from its parent node by 10 and adding the value of the current node.

The traversal can be done using either a depth-first search (DFS) or breadth-first search (BFS). DFS is commonly used for this type of problem since we need to follow each path to its leaves.

Method 1 - Recursive - Calculating Current Number and Sum

Here is the approach:

  • At each recursive call, pass the current sum calculated so far.
  • For every node, calculate the new sum as current_sum * 10 + node.val.
  • If the node is a leaf, add its value to the total sum.
  • Recursively process the left and right child nodes.
  • Edge case: If the tree is empty (root == null), return 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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

public int dfs(TreeNode node, int num, int sum) {
	if (node == null) {
		return sum;
	}

	num = num * 10 + node.val;

	// leaf
	if (node.left == null && node.right == null) {
		sum += num;
		return sum;
	}

	// left subtree + right subtree
	sum = dfs(node.left, num, sum) + dfs(node.right, num, sum);
	return sum;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], num: int, sum: int) -> int:
            if not node:
                return sum  # Base case: empty tree
            num = num * 10 + node.val
            
            if not node.left and not node.right:
                sum += num;
                return sum
            # Recur for left and right children
            sum = dfs(node.left, num, sum) + dfs(node.right, num, sum)
        
        return dfs(root, 0, 0)

Complexity

  • ⏰ Time complexity: O(n). Every node is visited once, so the time complexity is linear concerning the number of nodes.
  • 🧺 Space complexity:  O(h). The space complexity is determined by the recursion stack depth, which is proportional to the height h of the binary tree. In the worst case, a skewed binary tree gives h = n.

Method 2 - DFS and just use current num

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, int currentSum) {
        if (node == null) return 0; // Base case: empty subtree
        currentSum = currentSum * 10 + node.val; // Update current sum
        if (node.left == null && node.right == null) {
            return currentSum; // Leaf node, return the computed number
        }
        return dfs(node.left, currentSum) + dfs(node.right, currentSum); // Recur for children
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], cur_sum: int) -> int:
            if not node:
                return 0  # Base case: empty tree
            cur_sum = cur_sum * 10 + node.val  # Update current sum
            if not node.left and not node.right:
                return cur_sum  # Leaf node: return number
            # Recur for left and right children
            return dfs(node.left, cur_sum) + dfs(node.right, cur_sum)
        
        return dfs(root, 0)

Method 3 - Iterative Post Order Traversal

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public int sumNumbers(TreeNode root) {
	if (root == null) {
		return 0;
	}

	Stack<TreeNode> stack = new Stack<>();
	TreeNode cur = root;
	TreeNode pre = null;
	int curVal = 0;
	int sum = 0;

	while (cur != null || !stack.isEmpty()) {
		while (cur != null) {
			curVal = curVal * 10 + cur.val;
			stack.push(cur);
			cur = cur.left;
		}

		cur = stack.peek();
		if (cur.right != null && cur.right != pre) {
			cur = cur.right;
			continue;
		}

		if (cur.right == null && cur.left == null) {
			sum += curVal;
		}

		pre = stack.pop();
		curVal /= 10;
		cur = null;
	}

	return sum;
}

Complexity

  • Time Complexity: O(n). Each node is visited once.
  • Space Complexity: O(h). Stack space. n is total number of nodes in the tree and h is height of the tree.
    • In case of balanced tree (best case) it will be O(log n) and in case of Skewed Tree (worst case) it will be O(n)

Method 4 - Iterative Preorder Traversal

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public int sumNumbers(TreeNode root) {
	if (root == null) {
		return 0;
	}
	if (root.left == null && root.right == null) {
		return root.val;
	}

	Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque<>();
	stack.push(new Pair<>(root, root.val));

	int sum = 0;

	while (!stack.isEmpty()) {
		Pair<TreeNode, Integer> cur = stack.pop();
		TreeNode node = cur.getKey();
		int num = cur.getValue();

		if (node.left == null && node.right == null) {
			sum += num;
			continue;
		}
		
		if (node.right != null) {
			stack.push(new Pair<>(node.right, num * 10 + node.right.val));
		}
		if (node.left != null) {
			stack.push(new Pair<>(node.left, num * 10 + node.left.val));
		}
	}

	return sum;
}

Complexity

  • Time Complexity: O(n). Each node is visited once.
  • Space Complexity: O(h), for using stack space.
    • In case of balanced tree (best case) it will be O(log n) and in case of Skewed Tree (worst case) it will be O(n)