Sum Root to Leaf Numbers

LeetCode 129 | Difficulty: Medium

Medium

Problem Description

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`.

Topics: Tree, Depth-First Search, Binary Tree

---

Approach

Tree DFS

Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.

When to use

Path problems, subtree properties, tree structure manipulation.

---

Solutions

Solution 1: C# (Best: 100 ms)

Metric	Value
Runtime	100 ms
Memory	N/A
Date	2018-08-21

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int SumNumbers(TreeNode root) {
        if(root==null) return 0;
    int totalSum = 0;
    SumNumbers(root, 0, ref totalSum); 
    return totalSum;
}

public void SumNumbers(TreeNode root, int currentSum, ref int totalSum)
{
    if (root.left == null && root.right == null)
    {
        totalSum += currentSum*10+root.val;
        return;
    }
    if(root.left!=null) SumNumbers(root.left, currentSum*10+root.val, ref totalSum);
    if(root.right!=null) SumNumbers(root.right, currentSum*10+root.val, ref totalSum);
}

}

---

Complexity Analysis

Approach	Time	Space
Tree Traversal	$O(n)$	$O(h)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.