Path Sum II (All Root-to-Leaf Paths)

▶

Steps

setup

Initialize stack with root (5), path=[5], sum=5

Push (root=node5, path=[5], sum=5) onto the stack. Target=22. Result=[].

💡 The stack starts with just the root. Each entry bundles the node with the accumulated path and sum needed to reach it.

Line:

stack = [(root, [root.val], root.val)]

💡 We carry the full path (not just node) because we need it when we find a valid leaf.

expand

Pop root(5) - not leaf, push right(8) then left(4)

Pop (node5, [5], 5). Not a leaf (has left=4 and right=8). Push right child first: (node8, [5,8], 13). Then push left child: (node4, [5,4], 9). Left is on top so it's processed first.

💡 We push right before left so the left child is popped first (LIFO). This gives us a pre-order DFS going left.

Line:

node, path, current_sum = stack.pop()
if node.right:
    stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
if node.left:
    stack.append((node.left, path + [node.left.val], current_sum + node.left.val))

💡 path+[child.val] creates a new list for each branch - critical because different branches must have independent path copies.

expand

Pop node4 - not leaf, push node11 ([5,4,11], sum=20)

Pop (node4, [5,4], 9). Has left child node11, no right. Push (node11, [5,4,11], 20). Node4 has no right child so only one push.

💡 Node 4 is an internal node with only a left child. We push node11 with updated path and sum.

Line:

if node.left:
    stack.append((node.left, path + [node.left.val], current_sum + node.left.val))

💡 Sum is now 20, only 2 away from target 22. Node11's children are 7 and 2 - we need the child with val=2 to complete the path.

expand

Pop node11 - not leaf, push node2 then node7

Pop (node11, [5,4,11], 20). Has right=2 and left=7. Push right: (node2, [5,4,11,2], 22). Push left: (node7, [5,4,11,7], 27). Left (node7) is on top.

💡 Node 11 has two children. We push right (node2, sum=22) then left (node7, sum=27). Note that node2 will give us the answer.

Line:

if node.right:
    stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
if node.left:
    stack.append((node.left, path + [node.left.val], current_sum + node.left.val))

💡 The stack now has paths to both children of node11. node7 is processed first (top of stack) but won't match. node2 comes after.

expand

Pop node7 - leaf, sum=27 ≠ 22, no match

Pop (node7, [5,4,11,7], 27). It IS a leaf (no children). Check: 27 == 22? No. Skip. Do not add to results.

💡 Node 7 gives path sum 27 which doesn't equal target 22. We simply skip this leaf and the path is discarded.

Line:

if not node.left and not node.right:  # leaf
    if current_sum == targetSum:
        res.append(path)
    # else: discard silently

💡 No backtracking needed - the path list is already a separate copy. We just don't append to results.

reconstruct

Pop node2 - leaf, sum=22 == 22 → FOUND path [5,4,11,2]

Pop (node2, [5,4,11,2], 22). Leaf (no children). Check: 22 == 22? YES! Append [5,4,11,2] to results.

💡 First valid path found. 5+4+11+2=22. The path is already fully built in the stack entry - we just append it directly.

Line:

if not node.left and not node.right:
    if current_sum == targetSum:
        res.append(path)  # path = [5,4,11,2]

💡 The iterative approach avoids the explicit backtracking needed in recursive DFS. Each path is an independent copy.

expand

Pop node8 - not leaf, push node4(right-sub) [5,8,4] and node13

Pop (node8, [5,8], 13). Has left=13 and right=4(right subtree). Push right: (node4_right, [5,8,4], 17). Push left: (node13, [5,8,13], 26). Left (node13) on top.

💡 Now processing the right subtree of root. Node 8's children are 13 (left) and 4 (right). Both pushed with their paths.

Line:

if node.right:
    stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
if node.left:
    stack.append((node.left, path + [node.left.val], current_sum + node.left.val))

💡 Left subtree (node13) has sum 26 - won't reach 22. Right subtree (node4 with children 5,1) may have a valid path.

expand

Pop node13 - leaf, sum=26 ≠ 22, discard

Pop (node13, [5,8,13], 26). Leaf. 26 ≠ 22 → discard. Stack now has only node4_right.

💡 Node 13 is a leaf with path sum 26 - doesn't match. Discarded silently.

Line:

if not node.left and not node.right:
    if current_sum == targetSum:
        res.append(path)  # 26 != 22, skip

💡 The right subtree's left branch (sum 26) is too large. We move to the right branch of node8.

expand

Pop node4(right) - push node1(val=1) and node5(val=5)

Pop (node4_right, [5,8,4], 17). Has left=5 and right=1. Push right: (node1_leaf, [5,8,4,1], 18). Push left: (node5_leaf, [5,8,4,5], 22). Left on top.

💡 Node 4 (right subtree) has children 5 and 1. Left child (val=5, sum=22) is the second valid path!

Line:

if node.right:
    stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
if node.left:
    stack.append((node.left, path + [node.left.val], current_sum + node.left.val))

💡 Left child (val=5) gives sum 22 - the second answer. Right child (val=1) gives sum 18 - no match.

reconstruct

Pop node_val5 - leaf, sum=22 == 22 → FOUND [5,8,4,5]

Pop (node_val5, [5,8,4,5], 22). Leaf. 22 == 22 → append [5,8,4,5] to results. Both paths found.

💡 Second valid path found: 5+8+4+5=22. Now results has two entries.

Line:

if not node.left and not node.right:
    if current_sum == targetSum:
        res.append(path)  # path = [5,8,4,5]

💡 Both valid paths have been found. The remaining stack entry (node_val1, sum=18) will be popped but discarded as a leaf with sum≠22.

reconstruct

Pop node_val1 - leaf, sum=18 ≠ 22, discard. Stack empty.

Pop (node_val1, [5,8,4,1], 18). Leaf. 18 ≠ 22 → discard. Stack is now empty. Return result = [[5,4,11,2],[5,8,4,5]].

💡 Last leaf processed. Sum 18 doesn't match. Algorithm ends with two valid paths found.

Line:

# stack empty → while loop ends
return res  # [[5,4,11,2],[5,8,4,5]]

💡 The DFS explored the entire tree finding exactly the two paths that sum to 22.

from typing import List, Optional

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

def pathSum(root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
    if not root:
        return []
    res = []
    stack = [(root, [root.val], root.val)]
    while stack:
        node, path, current_sum = stack.pop()
        if not node.left and not node.right:
            if current_sum == targetSum:
                res.append(path)
        if node.right:
            stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
        if node.left:
            stack.append((node.left, path + [node.left.val], current_sum + node.left.val))
    return res

# Example usage same as before

📊

Path Sum II - Watch Iterative DFS Path Tracking Execute, Step by Step

The iterative approach avoids Python recursion limits. Each stack entry is a snapshot: node + path accumulated to reach it + sum accumulated. When we pop a leaf that sums to 22, we record the path.

Current node: 1

548111347251

DFS Stack

1 (entered)path=[5] sum=5

Current node: 2

548111347251

DFS Stack

2 (entered)path=[5,4] sum=93 (entered)path=[5,8] sum=13

Current node: 4

5481172

DFS Stack

4 (entered)path=[5,4,11] sum=203 (entered)path=[5,8] sum=13

Current node: 7

11728

DFS Stack

7 (entered)path=[5,4,11,7] sum=278 (entered)path=[5,4,11,2] sum=223 (entered)path=[5,8] sum=13

Current node: 8

728

DFS Stack

8 (entered)path=[5,4,11,2] sum=223 (entered)path=[5,8] sum=13

Current node: 3

28134

DFS Stack

3 (entered)path=[5,8] sum=13

Result: [5,4,11,2]

Current node: 5

8134

DFS Stack

5 (entered)path=[5,8,13] sum=266 (entered)path=[5,8,4] sum=17

Result: [5,4,11,2]

Current node: 6

13451

DFS Stack

6 (entered)path=[5,8,4] sum=17

Result: [5,4,11,2]

Current node: 9

451

DFS Stack

9 (entered)path=[5,8,4,5] sum=2210 (entered)path=[5,8,4,1] sum=18

Result: [5,4,11,2]

Current node: 10

51

DFS Stack

10 (entered)path=[5,8,4,1] sum=18

Result: [5,4,11,2, 5,8,4,5]

548111347251

Result: [5,4,11,2, 5,8,4,5]

Return: [[5,4,11,2],[5,8,4,5]]

Key Takeaways

✓ Carrying (node, path, sum) in each stack entry eliminates the need for explicit backtracking - each branch has its own independent path copy.

In recursive DFS you'd pass path by reference and undo changes after recursion. Here each stack entry owns its path.

✓ Push right before left so left is processed first - this gives the same traversal order as recursive DFS.

Stacks are LIFO: last pushed = first popped. To process left first, push right first.

✓ Only leaf nodes (no children) are checked against targetSum. Internal nodes just push their children.

Root-to-leaf paths always end at leaves. Checking at every node would give false positives for internal paths.

Practice

1. You need to determine if a binary tree is height-balanced, meaning the heights of the two child subtrees of any node never differ by more than one. Which approach guarantees an optimal O(n) time solution without redundant height computations?

easy

A. Use a top-down recursive approach that checks balance only at the root node.

B. Compute height for each node separately and check balance at each node recursively.

C. Perform a breadth-first traversal and check balance by comparing subtree sizes at each level.

D. Use a postorder traversal that returns height and balance status simultaneously, stopping early if imbalance is found.

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking balance at every node efficiently without recomputing heights multiple times.

2. Step 2: Identify the approach that avoids redundant work

   Postorder traversal that returns both height and balance status in one pass allows early exit on imbalance and avoids repeated height calculations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Postorder traversal with early exit is O(n) and avoids recomputation [OK]

Hint: Postorder traversal with early exit avoids repeated height calls [OK]

Common Mistakes:

• Checking balance only at root misses subtree imbalances
• Computing height separately for each node causes O(n²) time
• Using BFS to check balance is incorrect as balance depends on subtree heights

2. Consider this buggy iterative postorder traversal code:

def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited == peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result

What is the bug in this code?

medium

A. The inner while loop should traverse right children instead of left

B. The condition should check if last_visited != peek_node.right, not == peek_node.right

C. The last_visited variable is never updated

D. The result list is appended before traversing the left subtree

Solution

1. Step 1: Examine condition for traversing right subtree

   Correct logic requires moving to right child if it exists and was not visited yet, so condition must be last_visited != peek_node.right.

2. Step 2: Identify effect of wrong condition

   Using last_visited == peek_node.right causes skipping right subtree traversal or infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Fixing condition restores correct postorder traversal [OK]

Hint: Check last_visited != right child to avoid revisiting [OK]

Common Mistakes:

• Using == instead of !=
• Not updating last_visited
• Appending too early

3. What is the time complexity of the optimized iterative approach using a stack and a hash map to build a binary tree from preorder and inorder traversals of length n?

medium

A. O(n^2) due to nested loops scanning preorder and inorder arrays

B. O(n log n) due to hash map lookups for inorder indices

C. O(n) because each node is pushed and popped at most once from the stack

D. O(n) but with O(n^2) auxiliary space for recursion stack

Solution

1. Step 1: Analyze main loops

   The algorithm iterates preorder once, pushing and popping nodes from stack at most once each.

2. Step 2: Consider hash map lookups

   Hash map lookups for inorder indices are O(1) each, so no extra log factor.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Each node processed once with O(1) operations [OK]

Hint: Each node pushed and popped once; hash map lookups O(1) [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing hash map lookup cost
• Counting recursion stack space in iterative approach

4. What is the space complexity of the optimized recursive DFS approach for checking if a binary tree is symmetric, assuming the tree has n nodes and height h?

medium

A. O(h) due to recursion stack depth proportional to tree height

B. O(1) since no extra space besides variables is used

C. O(n) because all nodes are stored in an auxiliary data structure

D. O(n) due to storing all nodes in a queue for BFS

Solution

1. Step 1: Identify recursion stack usage

   The recursive calls go as deep as the height of the tree, so the recursion stack uses O(h) space.

2. Step 2: Confirm no additional data structures store all nodes

   The algorithm does not use queues or arrays to store nodes; it only uses call stack and local variables.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Recursion stack space depends on tree height, not total nodes [OK]

Hint: Recursion stack space = tree height, not total nodes [OK]

Common Mistakes:

• Confusing BFS queue space with DFS recursion stack
• Assuming O(n) space due to node storage
• Ignoring recursion stack space

5. Suppose you want to perform a preorder traversal on a binary tree where nodes can have parent pointers but no left or right pointers. Which approach correctly adapts preorder traversal to this scenario without extra space?

hard

A. Use a modified iterative approach that tracks previously visited nodes to avoid revisiting

B. Use recursion on parent pointers to simulate traversal

C. Iteratively traverse using parent pointers and a stack to track visited nodes

D. Use Morris traversal by creating temporary threaded links on parent pointers

Solution

1. Step 1: Understand traversal constraints

   Without left/right pointers, standard Morris or recursion is not applicable; parent pointers only allow upward traversal.

2. Step 2: Identify correct approach

   Tracking previously visited nodes iteratively allows preorder traversal by moving up/down without extra space for recursion stack.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Modified iterative approach handles parent-only trees without extra space [OK]

Hint: Parent-only trees require tracking visited nodes iteratively [OK]

Common Mistakes:

• Trying to use recursion without child pointers
• Attempting Morris traversal on parent pointers
• Using stack without tracking visited nodes