Sum Root to Leaf Numbers

▶

Steps

setup

Initialize variables and start at root

Set total sum to 0, current_number to 0, and start traversal at the root node with value 1.

💡 Initialization sets up the variables needed to track the sum and the current path number as we traverse.

Line:

total = 0
current_number = 0
node = root

💡 We begin traversal at the root with no accumulated number or sum.

compare

Check if current node has left child

At node 1, check if left child exists. It does (node 2), so we proceed to find the predecessor in the left subtree.

💡 This decision determines whether to process the current node directly or to create a threaded link to traverse left subtree first.

Line:

if node.left is None:

💡 Finding predecessor helps us create a temporary link to return after left subtree traversal.

traverse

Find predecessor in left subtree

Start at node 2 (left child of 1) and find the rightmost node in this subtree. Node 2 has no right child, so it is the predecessor.

💡 Finding the predecessor allows us to create a temporary link back to the current node after left subtree traversal.

Line:

predecessor = node.left
while predecessor.right and predecessor.right != node:
    predecessor = predecessor.right

💡 The predecessor is the rightmost node in the left subtree, here node 2 itself.

expand

Create threaded link and update current_number

Since predecessor's right is null, set predecessor.right to current node (1), update current_number to 1, and move to left child (node 2).

💡 Creating the threaded link allows returning to node 1 after finishing left subtree traversal without recursion.

Line:

if predecessor.right is None:
    predecessor.right = node
    current_number = current_number * 10 + node.val
    node = node.left

💡 The current_number now includes node 1's value as the first digit in the path.

compare

At node 2, check left child is null

At node 2, check if left child exists. It does not, so we will process this node as a leaf candidate.

💡 This check determines if we can form a complete root-to-leaf number at this node.

Line:

if node.left is None:

💡 Leaf nodes or nodes without left children are processed directly in Morris traversal.

fill_cells

Process node 2 with no left child

At node 2, left child is null, so update current_number to 12 (1*10+2). Node 2 is a leaf, so add 12 to total. Then move to right child which is threaded link back to node 1.

💡 Processing leaf nodes is where the path number is complete and added to the total sum.

Line:

if node.left is None:
    current_number = current_number * 10 + node.val
    if node.left is None and node.right is None:
        total += current_number
    node = node.right
    current_number //= 10

💡 Leaf nodes finalize a root-to-leaf number which contributes to the sum.

shrink

Remove threaded link and backtrack

At node 1 again, predecessor is node 2. Since predecessor.right points to node 1, remove the threaded link, remove node 1's digit from current_number by dividing by 10, and move to right child (node 3).

💡 Removing the threaded link restores the original tree structure and backtracks the path number.

Line:

else:
    predecessor.right = None
    current_number //= 10 ** steps
    node = node.right

💡 Backtracking removes digits from current_number to reflect moving up the tree.

compare

At node 3, check left child is null

At node 3, check if left child exists. It does not, so we will process this node as a leaf candidate.

💡 This check determines if we can form a complete root-to-leaf number at this node.

Line:

if node.left is None:

💡 Leaf nodes or nodes without left children are processed directly in Morris traversal.

fill_cells

Process node 3 with no left child

At node 3, left child is null, so update current_number to 13 (1*10+3). Node 3 is a leaf, so add 13 to total. Then move to right child which is null.

💡 Processing the right leaf node completes the second root-to-leaf path number.

Line:

if node.left is None:
    current_number = current_number * 10 + node.val
    if node.left is None and node.right is None:
        total += current_number
    node = node.right
    current_number //= 10

💡 The second leaf node completes the second path number contributing to the sum.

reconstruct

Traversal complete, return total sum

No more nodes to visit (node is null), so return the total sum of all root-to-leaf numbers, which is 25.

💡 The algorithm finishes by returning the accumulated sum of all root-to-leaf numbers.

Line:

return total

💡 The final answer is the sum of all numbers formed from root to leaf paths.

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

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        total = 0  # STEP 1
        current_number = 0  # STEP 1
        node = root  # STEP 1
        while node:  # STEP 2 loop
            if node.left is None:  # STEP 2 check
                current_number = current_number * 10 + node.val  # STEP 5 update number
                if node.left is None and node.right is None:  # STEP 5 leaf check
                    total += current_number  # STEP 5 add to total
                node = node.right  # STEP 5 move right
                current_number //= 10  # STEP 5 backtrack number
            else:
                predecessor = node.left  # STEP 3 find predecessor
                steps = 1  # STEP 3 count steps
                while predecessor.right and predecessor.right != node:  # STEP 3 loop
                    predecessor = predecessor.right  # STEP 3 move right
                    steps += 1  # STEP 3 increment steps
                if predecessor.right is None:  # STEP 4 create thread
                    predecessor.right = node  # STEP 4 link
                    current_number = current_number * 10 + node.val  # STEP 4 update number
                    node = node.left  # STEP 4 move left
                else:  # STEP 6 remove thread
                    predecessor.right = None  # STEP 6 unlink
                    if not node.left and not node.right:  # STEP 6 leaf check
                        total += current_number  # STEP 6 add to total
                    current_number //= 10 ** steps  # STEP 6 backtrack number
                    node = node.right  # STEP 6 move right
        return total  # STEP 8 return result

📊

Sum Root to Leaf Numbers - Watch the Algorithm Execute, Step by Step

Watching this step-by-step traversal reveals how the algorithm cleverly modifies the tree temporarily to avoid recursion, and how it accumulates path numbers only at leaf nodes.

Current node: 1

123

Current node: 1

123

Current node: 1

123

Current node: 2

123

Current node: 2

123

Current node: 1

123

Current node: 3

123

Current node: 3

123

123

123

Return: 25

Key Takeaways

✓ Morris traversal uses temporary threaded links to traverse the tree without recursion or extra space.

This is hard to see from code alone because the tree structure is modified and restored dynamically.

✓ The current_number variable accumulates digits as we go down the tree and backtracks correctly when returning up.

Watching the number build and shrink visually clarifies how path numbers are formed and discarded.

✓ Leaf nodes trigger the addition of the current path number to the total sum, marking completion of a root-to-leaf path.

Seeing exactly when and why the sum updates helps understand the problem's core logic.

Practice

1. You are given a binary tree and a target sum. The task is to find all root-to-leaf paths where the sum of the node values equals the target sum. Which algorithmic approach guarantees finding all such paths efficiently?

easy

A. Greedy traversal choosing the child with the closest value to the remaining sum

B. Depth-first search (DFS) with path tracking and backtracking to explore all root-to-leaf paths

C. Dynamic programming to store sums at each node and combine results bottom-up

D. Breadth-first search (BFS) with queue to find the shortest path matching the sum

Solution

1. Step 1: Understand problem requires all root-to-leaf paths

   Since we must find all paths, not just one, exhaustive exploration is needed.

2. Step 2: Identify DFS with path tracking and backtracking

   DFS explores each path fully, tracking the current path and sum, backtracking to explore alternatives.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DFS explores all paths, greedy or BFS do not guarantee all paths [OK]

Hint: All root-to-leaf paths require exhaustive DFS [OK]

Common Mistakes:

• Thinking greedy or BFS finds all paths
• Confusing DP for path enumeration

2. Consider this modified Morris inorder traversal code snippet. Which line contains a subtle bug that can cause infinite loops or incorrect output on some trees?

def inorderTraversal(root):
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current  # create thread
                current = current.left
            else:
                # BUG: missing line to remove thread
                result.append(current.val)
                current = current.right
    return result

medium

A. Missing line resetting predecessor.right = None to remove thread

B. Line moving current to current.left after creating thread

C. Line appending current.val after detecting thread

D. Line setting predecessor.right = current (creating thread)

Solution

1. Step 1: Identify thread removal step

   Morris traversal requires removing the temporary thread by setting predecessor.right = None after visiting the node.

2. Step 2: Locate missing removal

   The code lacks the line resetting predecessor.right = None, causing infinite loops or corrupted tree structure.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without removing thread, traversal loops endlessly [OK]

Hint: Always remove threads to restore tree [OK]

Common Mistakes:

• Forgetting to remove thread
• Appending node before removing thread
• Incorrectly creating thread

3. What is the time complexity of the optimal DFS with two-value return solution for the House Robber III problem on a tree with n nodes?

medium

A. O(n^2) due to checking grandchildren nodes explicitly

B. O(n) but with extra O(n) space for memoization arrays

C. O(n) because each node is visited once in DFS

D. O(n log n) because of recursive calls and combining results

Solution

1. Step 1: Identify DFS traversal cost

   The algorithm visits each node exactly once in a postorder DFS traversal.

2. Step 2: Analyze operations per node

   At each node, constant time operations are done: combining left and right child results, no repeated work.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal of n nodes -> O(n) time [OK]

Hint: DFS visits each node once, no repeated subproblems [OK]

Common Mistakes:

• Assuming O(n^2) due to grandchildren checks
• Confusing recursion stack space with time complexity

4. Suppose the problem is modified so that node values can be negative, and you want to find all root-to-leaf paths summing to targetSum. Which modification to the DFS approach is necessary to ensure correctness?

hard

A. Remove pruning and explore all paths fully since negative values can reduce sums

B. Add pruning to stop exploring paths when current_sum exceeds targetSum

C. Use BFS instead of DFS to avoid infinite loops caused by negative values

D. Sort children nodes by value to explore promising paths first

Solution

1. Step 1: Understand effect of negative values

   Negative values can decrease current_sum, so pruning based on exceeding targetSum can miss valid paths.

2. Step 2: Adjust DFS to remove pruning

   To ensure all valid paths are found, pruning must be removed and all paths fully explored.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Pruning breaks correctness with negative values; full exploration needed [OK]

Hint: Negative values invalidate pruning based on sum limits [OK]

Common Mistakes:

• Applying pruning blindly
• Switching to BFS unnecessarily

5. Suppose the Path Sum problem is modified so that node values can be negative, and you want to find if any root-to-leaf path sums exactly to targetSum. Which of the following changes to the DFS approach is necessary to handle this correctly?

hard

A. Precompute all path sums and store them in a hash set for O(1) lookup

B. Add memoization to avoid revisiting nodes with the same current sum

C. Use BFS instead of DFS to guarantee shortest path sum

D. Remove early stopping because negative values can invalidate pruning assumptions

Solution

1. Step 1: Understand impact of negative values

   Negative values mean partial sums can decrease later, so pruning based on current sum is unsafe.

2. Step 2: Adjust algorithm accordingly

   Early stopping based on partial sums must be removed to avoid missing valid paths.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Negative values break pruning assumptions, so early stopping must be disabled [OK]

Hint: Negative values invalidate pruning, so no early stopping [OK]

Common Mistakes:

• Assuming early stopping always works
• Switching to BFS unnecessarily