Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonGoogleFacebook

Sum Root to Leaf Numbers

Choose your preparation mode4 modes available
📋
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
}
0/9
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
t1_01basic
Input{"root":[1,2,3]}
Expected25

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

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

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

t2_01edge
Input{"root":[0]}
Expected0

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

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

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

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

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

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

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

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

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.

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

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

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]}
⏱ Performance - must finish in 2000ms

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

Practice

(1/5)
1. Consider the following code snippet implementing the optimal countNodes function for a complete binary tree. Given the tree: 1 / \ 2 3 / 4 What is the final return value of countNodes(root)?
easy
A. 4
B. 3
C. 5
D. 6

Solution

  1. Step 1: Calculate tree height

    Height h = 3 (nodes 1 -> 2 -> 4).
  2. Step 2: Binary search on last level nodes

    Last level has indices 0 to 3. Check existence: - idx=0 exists (node 4) - idx=1 does not exist So left ends at 1.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Count = (2^(3-1)-1) + left = 3 + 1 = 4 [OK]
Hint: Count = perfect nodes + last level nodes found [OK]
Common Mistakes:
  • Off-by-one in binary search bounds
  • Miscounting last level nodes
2. Consider the following code implementing the optimal House Robber III solution. Given the tree: 3 / \ 2 3 \ \ 3 1 What is the value of rob_current when dfs is called on the root node (value 3)?
easy
A. 7
B. 6
C. 8
D. 9

Solution

  1. Step 1: Trace dfs on left child (value 2)

    dfs(2) calls dfs(null) and dfs(3). dfs(null) returns (0,0). dfs(3) returns (3,0) because it has no children. So rob_current=3+0+0=3, not_rob_current=max(0,0)+max(0,0)=0. dfs(3) returns (3,0). For node 2: rob_current=2+0+0=2, not_rob_current=max(0,3)+max(0,0)=3. dfs(2) returns (2,3).
  2. Step 2: Trace dfs on right child (value 3)

    dfs(3) calls dfs(null) and dfs(1). dfs(1) returns (1,0). So rob_current=3+0+0=3, not_rob_current=max(0,0)+max(1,0)=1. dfs(3) returns (3,1).
  3. Step 3: Calculate rob_current at root (value 3)

    rob_current = 3 + left[1] + right[1] = 3 + 3 + 1 = 7.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Sum matches known example output 7 [OK]
Hint: Add node.val + not_rob of children for rob_current [OK]
Common Mistakes:
  • Mixing rob and not_rob values for children
  • Off-by-one in recursion returns
3. Consider the following buggy code snippet for building a binary tree from preorder and inorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or infinite loops?
medium
A. Line where stack is initialized with root
B. Line inside if block missing stack.append(node.left)
C. Line where root is initialized with preorder[0]
D. Line inside else block where inorder_index is incremented

Solution

  1. Step 1: Identify missing operation

    Inside the if block, after creating node.left, the new node is not pushed onto the stack.
  2. Step 2: Consequences of missing stack append

    Without pushing, the algorithm loses track of the left subtree root, causing incorrect tree or infinite loops.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Stack must track all nodes to correctly build tree [OK]
Hint: Always push newly created nodes to stack to track subtree roots [OK]
Common Mistakes:
  • Forgetting to push left child nodes
  • Incorrectly incrementing inorder_index
  • Misinitializing root or stack
4. 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
5. Suppose you want to perform inorder traversal on a binary tree where nodes can have parent pointers but no left or right child pointers. Which approach correctly produces the inorder sequence without recursion or extra stack?
hard
A. Use Morris traversal by creating threads on parent pointers instead of child pointers.
B. Use breadth-first search since parent pointers allow level order traversal.
C. Use recursive traversal ignoring parent pointers, which will fail due to missing child links.
D. Use iterative traversal with a pointer to the current node and track previously visited node to decide traversal direction.

Solution

  1. Step 1: Understand traversal constraints

    Without left/right child pointers, Morris traversal is not applicable since it relies on child links.
  2. Step 2: Use parent pointers to simulate traversal

    By tracking current and previously visited nodes, we can move up or down the tree to simulate inorder traversal iteratively.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Tracking previous node enables correct traversal without extra space [OK]
Hint: Parent pointers + prev node tracking enable traversal [OK]
Common Mistakes:
  • Trying to create threads on parent pointers
  • Using recursion without child pointers
  • Confusing BFS with inorder traversal
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard