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 are given two arrays representing the inorder and postorder traversal sequences of a binary tree. Which approach guarantees reconstructing the original tree efficiently without redundant searches?

easy

A. Use a greedy approach by always attaching nodes as left children when possible.

B. Use dynamic programming to store subtrees and avoid recomputation.

C. Use recursion with a hash map to quickly find root indices in the inorder array.

D. Use breadth-first search to reconstruct the tree level by level.

Solution

1. Step 1: Understand the problem constraints

   Reconstructing a tree from inorder and postorder requires identifying root nodes and splitting subtrees efficiently.

2. Step 2: Evaluate approaches

   Recursion with a hash map allows O(1) root index lookup in inorder, avoiding repeated linear searches and ensuring O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map lookup avoids O(n) search per recursion [OK]

Hint: Hash map lookup avoids repeated linear searches [OK]

Common Mistakes:

• Assuming greedy or BFS can reconstruct tree uniquely
• Confusing DP with tree construction
• Ignoring index lookup cost

2. The following code attempts to check if a binary tree is balanced using iterative postorder traversal. Which line contains a subtle bug that can cause incorrect results on an empty tree or null root?

medium

A. Line 1: Missing check for empty root before traversal

B. Line 7: Incorrectly pushing node.left without null check

C. Line 12: Comparing last_visited with peek.right incorrectly

D. Line 16: Using abs difference without considering null children

Solution

1. Step 1: Identify handling of empty tree

   The code does not check if root is None before starting traversal, which can cause errors or incorrect results.

2. Step 2: Verify other lines

   Other lines handle null children safely using heights.get with default 0, and last_visited logic is correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing early return for empty root causes bug [OK]

Hint: Always check for empty root before traversal [OK]

Common Mistakes:

• Forgetting to handle empty tree as balanced
• Incorrectly comparing last_visited causing infinite loops
• Not defaulting heights for null children

3. What is the time complexity of the brute force recursive approach that computes the diameter of a binary tree by calculating the height at each node separately?

medium

A. O(n log n)

B. O(n)

C. O(n^2)

D. O(n^3)

Solution

1. Step 1: Analyze the height function calls.

   Height is called for each node, and each call traverses its subtree, leading to repeated traversals.

2. Step 2: Calculate total complexity.

   For each of the n nodes, height is computed which can take O(n) in worst case, resulting in O(n^2) total time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Repeated height computations cause quadratic time [OK]

Hint: Repeated height calls cause O(n^2) time, not O(n) [OK]

Common Mistakes:

• Assuming height calls are O(1)
• Confusing recursion stack space with time
• Thinking it's O(n log n) due to balanced tree

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

5. Suppose the problem is modified so that the binary tree nodes can be reused multiple times in the flattened linked list (i.e., nodes can appear multiple times). Which modification to the optimal flatten algorithm is necessary to handle this correctly?

hard

A. No change needed; the current in-place reverse preorder traversal works as is.

B. Use a preorder traversal to collect nodes in a list and rebuild the linked list allowing duplicates.

C. Modify the algorithm to clone nodes during traversal to allow multiple appearances.

D. Switch to a postorder traversal to ensure all duplicates are appended after processing children.

Solution

1. Step 1: Understand reuse requirement

   Allowing nodes to appear multiple times means the original nodes cannot be simply rewired in-place without duplication.

2. Step 2: Identify necessary modification

   Cloning nodes during traversal is required to create multiple instances, preserving original tree structure and allowing duplicates.

3. Step 3: Why other options fail

   No change needed; the current in-place reverse preorder traversal works as is. fails because in-place rewiring destroys original nodes. Use a preorder traversal to collect nodes in a list and rebuild the linked list allowing duplicates. collects nodes but does not clone them. Switch to a postorder traversal to ensure all duplicates are appended after processing children. traversal order does not address duplication.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Cloning nodes enables multiple appearances in flattened list [OK]

Hint: Cloning nodes is needed for multiple appearances [OK]

Common Mistakes:

• Assuming in-place rewiring supports duplicates
• Collecting nodes without cloning leads to lost references
• Changing traversal order alone does not solve duplication