Sum Root to Leaf Numbers

Problem Statement

You are given the root of a binary tree containing digits from 0-9 only. Each root-to-leaf path represents a number. Return the total sum of all numbers represented by root-to-leaf paths.

Examples

Input	Output	Calculation
`[1,2,3]`	25	12 + 13
`[4,9,0,5,1]`	1026	495 + 491 + 40

Constraints

The number of nodes is in the range [1, 1000].
0 <= Node.val <= 9

Real-World Applications

Complexity Comparison

Approach	Time	Space	Best When
DFS	O(n)	O(h)	Simple, clean; h is height
BFS	O(n)	O(w)	Avoid recursion; w is max width

Approach 1: DFS

★ Recommended

Recursively traverse with current_sum multiplied by 10 and incremented by current digit. Sum leaf values.

⏱ Time O(n) Visit each node once 💾 Space O(h) Recursion depth

Solution Code

from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def sumNumbers(root: Optional[TreeNode]) -> int:
    """
    Sum all root-to-leaf numbers using DFS.
    Build number by appending digits as we traverse down.
    Time: O(n), Space: O(h) for recursion stack
    """
    def dfs(node, current_sum):
        if not node:
            return 0

        # Build number: multiply by 10 and add current digit
        current_sum = current_sum * 10 + node.val

        # Leaf node: return the complete number
        if not node.left and not node.right:
            return current_sum

        # Recursively process children and sum
        return dfs(node.left, current_sum) + dfs(node.right, current_sum)

    return dfs(root, 0)


# Test cases
if __name__ == "__main__":
    # Example 1: [1,2,3]
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)

    print(sumNumbers(root))  # 25 (12 + 13)

    # Example 2: [4,9,0,5,1]
    root2 = TreeNode(4)
    root2.left = TreeNode(9)
    root2.right = TreeNode(0)
    root2.left.left = TreeNode(5)
    root2.left.right = TreeNode(1)

    print(sumNumbers(root2))  # 1026 (495 + 491 + 40)

    # Example 3: Single node
    single = TreeNode(0)
    print(sumNumbers(single))  # 0

#include <iostream>
#include <algorithm>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        /**
         * Sum all root-to-leaf numbers using DFS.
         * Build number by appending digits as we traverse down.
         * Time: O(n), Space: O(h) for recursion stack
         */
        return dfs(root, 0);
    }

private:
    int dfs(TreeNode* node, int current_sum) {
        if (!node) return 0;

        // Build number: multiply by 10 and add current digit
        current_sum = current_sum * 10 + node->val;

        // Leaf node: return the complete number
        if (!node->left && !node->right) {
            return current_sum;
        }

        // Recursively process children and sum
        return dfs(node->left, current_sum) + dfs(node->right, current_sum);
    }
};

// Test cases
int main() {
    // Example 1: [1,2,3]
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);

    Solution sol;
    cout << "Example 1 sum: " << sol.sumNumbers(root) << endl;  // 25 (12 + 13)

    // Example 2: [4,9,0,5,1]
    TreeNode* root2 = new TreeNode(4);
    root2->left = new TreeNode(9);
    root2->right = new TreeNode(0);
    root2->left->left = new TreeNode(5);
    root2->left->right = new TreeNode(1);

    cout << "Example 2 sum: " << sol.sumNumbers(root2) << endl;  // 1026 (495 + 491 + 40)

    return 0;
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private int dfs(TreeNode node, int currentSum) {
        if (node == null) return 0;

        // Build number: multiply by 10 and add current digit
        currentSum = currentSum * 10 + node.val;

        // Leaf node: return the complete number
        if (node.left == null && node.right == null) {
            return currentSum;
        }

        // Recursively process children and sum
        return dfs(node.left, currentSum) + dfs(node.right, currentSum);
    }

    /**
     * Sum all root-to-leaf numbers using DFS.
     * Build number by appending digits as we traverse down.
     * Time: O(n), Space: O(h) for recursion stack
     */
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
}

class Main {
    public static void main(String[] args) {
        // Example 1: [1,2,3]
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        Solution sol = new Solution();
        System.out.println("Example 1 sum: " + sol.sumNumbers(root));  // 25 (12 + 13)

        // Example 2: [4,9,0,5,1]
        TreeNode root2 = new TreeNode(4);
        root2.left = new TreeNode(9);
        root2.right = new TreeNode(0);
        root2.left.left = new TreeNode(5);
        root2.left.right = new TreeNode(1);

        System.out.println("Example 2 sum: " + sol.sumNumbers(root2));  // 1026 (495 + 491 + 40)
    }
}

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

/**
 * Sum all root-to-leaf numbers using DFS.
 * Build number by appending digits as we traverse down.
 * Time: O(n), Space: O(h) for recursion stack
 * @param {TreeNode} root
 * @return {number}
 */
function sumNumbers(root) {
    function dfs(node, currentSum) {
        if (!node) return 0;

        // Build number: multiply by 10 and add current digit
        currentSum = currentSum * 10 + node.val;

        // Leaf node: return the complete number
        if (!node.left && !node.right) {
            return currentSum;
        }

        // Recursively process children and sum
        return dfs(node.left, currentSum) + dfs(node.right, currentSum);
    }

    return dfs(root, 0);
}

// Test cases
const root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);

console.log("Example 1 sum:", sumNumbers(root1));  // 25 (12 + 13)

const root2 = new TreeNode(4);
root2.left = new TreeNode(9);
root2.right = new TreeNode(0);
root2.left.left = new TreeNode(5);
root2.left.right = new TreeNode(1);

console.log("Example 2 sum:", sumNumbers(root2));  // 1026 (495 + 491 + 40)

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * Sum all root-to-leaf numbers using DFS.
 * Build number by appending digits as we traverse down.
 * Time: O(n), Space: O(h) for recursion stack
 */
pub fn sum_numbers(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn dfs(node: Option<Rc<RefCell<TreeNode>>>, current_sum: i32) -> i32 {
        match node {
            None => 0,
            Some(n) => {
                let node_ref = n.borrow();
                let val = node_ref.val;
                let left = node_ref.left.clone();
                let right = node_ref.right.clone();
                drop(node_ref);

                // Build number: multiply by 10 and add current digit
                let current_sum = current_sum * 10 + val;

                // Leaf node: return the complete number
                if left.is_none() && right.is_none() {
                    return current_sum;
                }

                // Recursively process children and sum
                dfs(left, current_sum) + dfs(right, current_sum)
            }
        }
    }

    dfs(root, 0)
}

fn main() {
    println!("Example 1: Sum root to leaf numbers with DFS");
}

package main

import "fmt"

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

/**
 * Sum all root-to-leaf numbers using DFS.
 * Build number by appending digits as we traverse down.
 * Time: O(n), Space: O(h) for recursion stack
 */
func sumNumbers(root *TreeNode) int {
    return dfs(root, 0)
}

func dfs(node *TreeNode, currentSum int) int {
    if node == nil {
        return 0
    }

    // Build number: multiply by 10 and add current digit
    currentSum = currentSum*10 + node.Val

    // Leaf node: return the complete number
    if node.Left == nil && node.Right == nil {
        return currentSum
    }

    // Recursively process children and sum
    return dfs(node.Left, currentSum) + dfs(node.Right, currentSum)
}

func main() {
    fmt.Println("Example 1: Sum root to leaf numbers with DFS")
}

Approach 2: BFS Iterative

alternative

Use a queue with (node, current_number) pairs. Sum all leaf numbers encountered.

⏱ Time O(n) Visit each node once 💾 Space O(w) Queue size (max width)

Solution Code

from typing import Optional
from collections import deque


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def sumNumbers(root: Optional[TreeNode]) -> int:
    """
    Sum all root-to-leaf numbers using iterative BFS.
    Queue stores (node, current_number) pairs.
    Time: O(n), Space: O(w) where w is max width
    """
    if not root:
        return 0

    queue = deque([(root, root.val)])
    total = 0

    while queue:
        node, current_sum = queue.popleft()

        # Leaf node: add to total
        if not node.left and not node.right:
            total += current_sum
            continue

        if node.left:
            queue.append((node.left, current_sum * 10 + node.left.val))
        if node.right:
            queue.append((node.right, current_sum * 10 + node.right.val))

    return total


# Test cases
if __name__ == "__main__":
    # Example 1: [1,2,3]
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)

    print(sumNumbers(root))  # 25 (12 + 13)

    # Example 2: [4,9,0,5,1]
    root2 = TreeNode(4)
    root2.left = TreeNode(9)
    root2.right = TreeNode(0)
    root2.left.left = TreeNode(5)
    root2.left.right = TreeNode(1)

    print(sumNumbers(root2))  # 1026 (495 + 491 + 40)

    # Example 3: Single node
    single = TreeNode(0)
    print(sumNumbers(single))  # 0

#include <iostream>
#include <queue>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        /**
         * Sum all root-to-leaf numbers using iterative BFS.
         * Queue stores (node, current_number) pairs.
         * Time: O(n), Space: O(w) where w is max width
         */
        if (!root) return 0;

        queue<pair<TreeNode*, int>> q;
        q.push({root, root->val});
        int total = 0;

        while (!q.empty()) {
            auto [node, current_sum] = q.front();
            q.pop();

            // Leaf node: add to total
            if (!node->left && !node->right) {
                total += current_sum;
                continue;
            }

            if (node->left) {
                q.push({node->left, current_sum * 10 + node->left->val});
            }
            if (node->right) {
                q.push({node->right, current_sum * 10 + node->right->val});
            }
        }

        return total;
    }
};

// Test cases
int main() {
    // Example 1: [1,2,3]
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);

    Solution sol;
    cout << "Example 1 sum: " << sol.sumNumbers(root) << endl;  // 25 (12 + 13)

    // Example 2: [4,9,0,5,1]
    TreeNode* root2 = new TreeNode(4);
    root2->left = new TreeNode(9);
    root2->right = new TreeNode(0);
    root2->left->left = new TreeNode(5);
    root2->left->right = new TreeNode(1);

    cout << "Example 2 sum: " << sol.sumNumbers(root2) << endl;  // 1026 (495 + 491 + 40)

    return 0;
}

import java.util.Queue;
import java.util.LinkedList;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
}

class Pair {
    TreeNode node;
    int sum;

    Pair(TreeNode node, int sum) {
        this.node = node;
        this.sum = sum;
    }
}

class Solution {
    /**
     * Sum all root-to-leaf numbers using iterative BFS.
     * Queue stores (node, current_number) pairs.
     * Time: O(n), Space: O(w) where w is max width
     */
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;

        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(root, root.val));
        int total = 0;

        while (!queue.isEmpty()) {
            Pair pair = queue.poll();
            TreeNode node = pair.node;
            int currentSum = pair.sum;

            // Leaf node: add to total
            if (node.left == null && node.right == null) {
                total += currentSum;
                continue;
            }

            if (node.left != null) {
                queue.add(new Pair(node.left, currentSum * 10 + node.left.val));
            }
            if (node.right != null) {
                queue.add(new Pair(node.right, currentSum * 10 + node.right.val));
            }
        }

        return total;
    }
}

class Main {
    public static void main(String[] args) {
        // Example 1: [1,2,3]
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        Solution sol = new Solution();
        System.out.println("Example 1 sum: " + sol.sumNumbers(root));  // 25 (12 + 13)

        // Example 2: [4,9,0,5,1]
        TreeNode root2 = new TreeNode(4);
        root2.left = new TreeNode(9);
        root2.right = new TreeNode(0);
        root2.left.left = new TreeNode(5);
        root2.left.right = new TreeNode(1);

        System.out.println("Example 2 sum: " + sol.sumNumbers(root2));  // 1026 (495 + 491 + 40)
    }
}

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

/**
 * Sum all root-to-leaf numbers using iterative BFS.
 * Queue stores [node, current_number] pairs.
 * Time: O(n), Space: O(w) where w is max width
 * @param {TreeNode} root
 * @return {number}
 */
function sumNumbers(root) {
    if (!root) return 0;

    const queue = [[root, root.val]];
    let total = 0;

    while (queue.length > 0) {
        const [node, currentSum] = queue.shift();

        // Leaf node: add to total
        if (!node.left && !node.right) {
            total += currentSum;
            continue;
        }

        if (node.left) {
            queue.push([node.left, currentSum * 10 + node.left.val]);
        }
        if (node.right) {
            queue.push([node.right, currentSum * 10 + node.right.val]);
        }
    }

    return total;
}

// Test cases
const root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);

console.log("Example 1 sum:", sumNumbers(root1));  // 25 (12 + 13)

const root2 = new TreeNode(4);
root2.left = new TreeNode(9);
root2.right = new TreeNode(0);
root2.left.left = new TreeNode(5);
root2.left.right = new TreeNode(1);

console.log("Example 2 sum:", sumNumbers(root2));  // 1026 (495 + 491 + 40)

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * Sum all root-to-leaf numbers using iterative BFS.
 * Queue stores (node, current_number) pairs.
 * Time: O(n), Space: O(w) where w is max width
 */
pub fn sum_numbers(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    if root.is_none() {
        return 0;
    }

    let mut queue = VecDeque::new();
    let root_node = root.unwrap();
    let val = root_node.borrow().val;
    queue.push_back((root_node, val));
    let mut total = 0;

    while !queue.is_empty() {
        let (node, current_sum) = queue.pop_front().unwrap();
        let node_ref = node.borrow();

        // Leaf node: add to total
        if node_ref.left.is_none() && node_ref.right.is_none() {
            total += current_sum;
            continue;
        }

        if let Some(left) = node_ref.left.clone() {
            let left_val = left.borrow().val;
            queue.push_back((left, current_sum * 10 + left_val));
        }
        if let Some(right) = node_ref.right.clone() {
            let right_val = right.borrow().val;
            queue.push_back((right, current_sum * 10 + right_val));
        }
    }

    total
}

fn main() {
    println!("Example 1: Sum root to leaf numbers with BFS");
}

package main

import "fmt"

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

/**
 * Pair struct to hold node and sum
 */
type Pair struct {
    node      *TreeNode
    sum       int
}

/**
 * Sum all root-to-leaf numbers using iterative BFS.
 * Queue stores (node, current_number) pairs.
 * Time: O(n), Space: O(w) where w is max width
 */
func sumNumbers(root *TreeNode) int {
    if root == nil {
        return 0
    }

    queue := []Pair{{node: root, sum: root.Val}}
    total := 0

    for len(queue) > 0 {
        pair := queue[0]
        queue = queue[1:]

        node := pair.node
        currentSum := pair.sum

        // Leaf node: add to total
        if node.Left == nil && node.Right == nil {
            total += currentSum
            continue
        }

        if node.Left != nil {
            queue = append(queue, Pair{node: node.Left, sum: currentSum*10 + node.Left.Val})
        }
        if node.Right != nil {
            queue = append(queue, Pair{node: node.Right, sum: currentSum*10 + node.Right.Val})
        }
    }

    return total
}

func main() {
    fmt.Println("Example 1: Sum root to leaf numbers with BFS")
}

Sum Root to Leaf Numbers

Problem Statement

Examples

Constraints

Real-World Applications

Complexity Comparison

Approach 1: DFS

Solution Code

Approach 2: BFS Iterative

Solution Code

Related Problems

Interview Tips