Sum Root to Leaf Numbers

📋

Problem

Imagine you have a tree where each node holds a digit, and you want to find the sum of all numbers formed by root-to-leaf paths - like reading numbers off branches in a magical forest.

Given a binary tree where each node contains a single digit (0-9), each root-to-leaf path represents a number formed by concatenating the digits along the path. Return the total sum of all these numbers. A leaf is a node with no children.

The number of nodes in the tree is in the range [1, 10^5].Node values are digits from 0 to 9.

Edge cases: Single node tree → output is the node's valueTree with all nodes having value 0 → sum is 0Tree with only left children → sum is the single number formed by concatenation

</>

IDE

def sumNumbers(root: TreeNode) -> int:public int sumNumbers(TreeNode root)int sumNumbers(TreeNode* root)function sumNumbers(root)

def sumNumbers(root):
    # Write your solution here
    pass

class Solution {
    public int sumNumbers(TreeNode root) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int sumNumbers(TreeNode* root) {
    // Write your solution here
    return 0;
}

function sumNumbers(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for all inputs due to missing accumulation or leaf check.✅ Add current_number to total only at leaf nodes; update current_number = current_number * 10 + node.val at each node.

Wrong: Sum of only one root-to-leaf pathGreedy approach picking only one path instead of all paths.✅ Use DFS to explore all root-to-leaf paths and sum their values.

Wrong: Sum includes non-leaf nodesAdding current_number at internal nodes, not just leaves.✅ Add to total only when node.left == null and node.right == null.

Wrong: Incorrect concatenation of digits (off-by-one error)Incorrectly updating current_number or missing digits in path.✅ Update current_number = current_number * 10 + node.val at each node.

Wrong: Timeout or no output on large inputUsing exponential or inefficient traversal instead of O(n) DFS.✅ Implement DFS with O(n) time complexity, avoid recomputation.

✓

Test Cases

Now test your code on edge cases like single node and zero-valued trees.

Try tricky cases that expose greedy or partial path summation mistakes.

Prepare for performance testing with large input; optimize your DFS.

t1_01basic

Input{"root":[1,2,3]}

Expected25

⏱ Performance - must finish in 2000ms

There are two root-to-leaf paths: 1->2 represents 12, 1->3 represents 13. Sum is 12 + 13 = 25.

💡 Think about how to accumulate numbers along root-to-leaf paths.

💡 Use DFS to carry the current number formed so far and add at leaves.

💡 At each node, current_number = current_number * 10 + node.val; add to total at leaves.

Why it failed: Basic case failed - likely not accumulating numbers correctly along paths or missing leaf check. Fix by updating current_number = current_number * 10 + node.val and adding only at leaves.

✓ Core DFS accumulation and leaf detection logic is correct.

t1_02basic

Input{"root":[4,9,0,5,1]}

Expected1026

⏱ Performance - must finish in 2000ms

Paths: 4->9->5 = 495, 4->9->1 = 491, 4->0 = 40; sum = 495 + 491 + 40 = 1026.

💡 Try enumerating all root-to-leaf paths and summing their numeric values.

💡 Check that you add to total only when reaching leaf nodes (no children).

💡 Carry the current number as you traverse and add it to total at leaves.

Why it failed: Failed to handle multiple leaf paths or leaf detection; possibly adding intermediate nodes. Fix by adding to total only at leaves (nodes with no children).

✓ Correctly sums all root-to-leaf numbers.

t2_01edge

Input{"root":[0]}

Expected0

⏱ Performance - must finish in 2000ms

Single node tree with value 0; only one path with number 0.

💡 Check behavior when tree has only one node.

💡 Ensure leaf detection works for single node trees.

💡 Return the node's value directly if it's a leaf.

Why it failed: Fails single node case; possibly missing leaf check or returning 0 incorrectly. Fix by returning node.val if node is leaf.

✓ Handles single node trees correctly.

t2_02edge

Input{"root":[0,0,0,0,null,null,0]}

Expected0

⏱ Performance - must finish in 2000ms

All nodes have value 0; all root-to-leaf paths sum to 0.

💡 Test trees where all node values are zero.

💡 Ensure accumulation doesn't add unintended values.

💡 Sum should be zero regardless of path length if all digits are zero.

Why it failed: Fails zero-value tree; possibly adding non-zero values or miscalculating. Fix by correctly accumulating digits without adding extra values.

✓ Correctly sums zero-valued trees.

t2_03edge

Input{"root":[1,2,null,3,null,4]}

Expected1234

⏱ Performance - must finish in 2000ms

Tree with only left children forming path 1->2->3->4 representing 1234.

💡 Check behavior on skewed trees with only left children.

💡 Ensure path concatenation works correctly along single branch.

💡 Result should be the single number formed by concatenation of all node values.

Why it failed: Fails skewed left child tree; possibly missing nodes or incorrect concatenation. Fix by carrying current_number correctly down left children.

✓ Handles left-skewed trees correctly.

t3_01corner

Input{"root":[1,2,3,4,5,6,7]}

Expected522

⏱ Performance - must finish in 2000ms

Paths: 1->2->4=124, 1->2->5=125, 1->3->6=136, 1->3->7=137; sum=124+125+136+137=522.

💡 Beware of greedy approaches that pick only one path.

💡 Enumerate all root-to-leaf paths to sum all numbers.

💡 Use DFS to explore all branches, not just one.

Why it failed: Greedy approach failed by summing only one path; fix by exploring all root-to-leaf paths with DFS.

✓ Correctly sums all root-to-leaf paths.

t3_02corner

Input{"root":[1,0,1,0,null,null,1]}

Expected111

⏱ Performance - must finish in 2000ms

Paths: 1->0->0=100, 1->1=11; sum=100 + 11 = 111. The path 1->1->1 does not exist as a root-to-leaf path.

💡 Check that only root-to-leaf paths are counted, not partial paths.

💡 Verify leaf detection to avoid counting internal nodes as leaves.

💡 Add to total only when node has no children.

Why it failed: Incorrectly counting non-leaf nodes as leaves; fix by adding to total only at nodes with no children.

✓ Correctly counts only root-to-leaf paths.

t3_03corner

Input{"root":[9,9,9,9,null,null,9]}

Expected2097

⏱ Performance - must finish in 2000ms

Paths: 9->9->9=999 (leftmost leaf), 9->9->9=999 (rightmost leaf), 9->9=99 (middle leaf); sum=999+999+99=2097.

💡 Check for off-by-one errors in path concatenation.

💡 Ensure all leaf nodes are included in sum.

💡 Verify current_number calculation at each node.

Why it failed: Off-by-one error in concatenation or missing leaf paths; fix by correctly updating current_number and including all leaves.

✓ Correctly sums all leaf paths with repeated digits.

t4_01performance

Input{"root":[1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0]}

Expectednull

⏱ Performance - must finish in 2000ms

Large tree with 100 nodes to test O(n) DFS performance within 2 seconds.

💡 Use DFS with O(n) time complexity.

💡 Avoid recomputing paths or using exponential algorithms.

💡 Carry current number as you traverse without extra overhead.

Why it failed: TLE due to exponential or inefficient traversal; fix by using O(n) DFS with path accumulation.

✓ Efficient O(n) DFS traversal confirmed.

Practice

1. You need to output the values of a binary tree's nodes in the order: left subtree, node itself, then right subtree, without modifying the tree structure or using extra space proportional to the tree height. Which approach best fits this requirement?

easy

A. Use a breadth-first search (BFS) to visit nodes level by level.

B. Use a recursive preorder traversal that visits root, left, then right nodes.

C. Use Morris traversal to perform inorder traversal with O(1) extra space by temporarily modifying tree links.

D. Use a dynamic programming approach to store and reuse subtree results.

Solution

1. Step 1: Understand traversal order requirement

   Inorder traversal visits left subtree, then node, then right subtree, matching the problem's order.

2. Step 2: Identify approach with O(1) space

   Morris traversal achieves inorder traversal without recursion or stack by temporarily modifying tree pointers, restoring them after use.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Morris traversal is known for O(1) space inorder traversal [OK]

Hint: Morris traversal enables inorder with O(1) space [OK]

Common Mistakes:

• Confusing preorder with inorder traversal order
• Assuming BFS can produce inorder sequence
• Thinking DP applies to traversal order

2. Consider the following BFS-based Python code to compute the maximum depth of a binary tree. Given the tree below, what is the value of depth after the second iteration of the while loop? Tree structure: - Root node 1 - Left child 2 - Right child 3 - Left child of 2 is 4

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root):
    if root is None:
        return 0
    queue = deque([root])
    depth = 0
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1
    return depth

root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
print(maxDepth(root))

easy

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Trace first iteration of while loop

   Initially, queue contains root (1). level_size=1. After processing node 1, enqueue its children 2 and 3. Increment depth to 1.

2. Step 2: Trace second iteration of while loop

   Queue now has nodes 2 and 3. level_size=2. Process node 2 (enqueue 4), process node 3 (no children). Increment depth to 2.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Depth increments after each level processed; after second level depth=2 [OK]

Hint: Depth increments after processing each tree level [OK]

Common Mistakes:

• Counting nodes instead of levels
• Off-by-one in depth increment
• Ignoring children enqueueing

3. You are given a binary tree and a target sum. You need to determine if there exists a root-to-leaf path such that adding up all the values along the path equals the target sum. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Depth-first search (DFS) with early stopping upon finding a valid path

B. Greedy traversal choosing the child with the closest value to the target sum

C. Dynamic programming with memoization of partial sums at each node

D. Breadth-first search (BFS) exploring all paths level by level

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking if any root-to-leaf path sums to the target. This naturally fits a tree traversal pattern.

2. Step 2: Identify the best approach

   DFS with early stopping is optimal because it explores paths deeply and stops as soon as a valid path is found, avoiding unnecessary work.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DFS explores paths fully and stops early when possible [OK]

Hint: Early stopping DFS avoids unnecessary traversal [OK]

Common Mistakes:

• Believing greedy approach works for sums
• Confusing BFS with DFS for path sums

4. The following code attempts to compute the diameter of a binary tree using an optimized recursive approach. Identify the line containing the subtle bug that causes incorrect diameter calculation.

medium

A. Line 6: if not node: return 0

B. Line 9: diameter = max(diameter, left + right + 1)

C. Line 10: return 1 + max(left, right)

D. Line 2: diameter = 0

Solution

1. Step 1: Understand diameter definition counts edges, not nodes.

   The diameter is the number of edges on the longest path, so it should be left + right, not left + right + 1.

2. Step 2: Identify the bug line.

   Line 9 adds 1 incorrectly, causing diameter to be off by one.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Diameter must be sum of left and right heights (edges), not nodes [OK]

Hint: Diameter counts edges = left + right, not +1 [OK]

Common Mistakes:

• Adding 1 to diameter sum
• Not using nonlocal for diameter
• Returning wrong height value

5. The following code attempts to find the Lowest Common Ancestor using parent pointers. Identify the line containing the subtle bug that causes incorrect results when one node is ancestor of the other.

def lowestCommonAncestor(root, p, q):
    parent = {root: None}
    stack = [root]
    while p not in parent or q not in parent:
        node = stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)

    ancestors = set()
    while p:
        ancestors.add(p)
        p = parent[p]
    while q not in ancestors:
        q = parent[q]
    return q

medium

A. Line: while p not in parent or q not in parent:

B. Line: while p:

C. Line: while q not in ancestors:

D. Line: parent = {root: None}

Solution

1. Step 1: Analyze parent map construction loop

   The loop 'while p not in parent or q not in parent:' ensures both nodes are in the parent map before ancestor sets are built.

2. Step 2: Identify subtle bug

   If one node is ancestor of the other, the loop may terminate prematurely if only one node is in parent map, causing KeyError later.

3. Step 3: Explanation

   The bug is that the loop condition does not guarantee both nodes are fully processed in the parent map before ancestor traversal.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Loop condition must ensure both nodes are in parent map to avoid errors [OK]

Hint: Parent map construction loop must fully process both nodes [OK]

Common Mistakes:

• Assuming parent map always complete
• Ignoring incomplete parent map causing KeyError
• Misplacing bug in ancestor set loops