Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonFacebookGoogle

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

Choose your preparation mode4 modes available
▶
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.
📊
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.
Step 1/11
·Active fill★Answer cell
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/5)
1. Given the following iterative postorder traversal code, what is the final output when run on the tree: root = TreeNode(1, None, TreeNode(2, TreeNode(3)))?
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
easy
A. [2, 3, 1]
B. [1, 3, 2]
C. [3, 2, 1]
D. [3, 1, 2]

Solution

  1. Step 1: Trace traversal on given tree

    Start at root(1), go left (None), push 1. Then peek 1, right child is 2, move to 2, push 2, go left to 3, push 3, left None.
  2. Step 2: Process nodes in postorder

    3 has no children, append 3. Back to 2, right visited, append 2. Back to 1, right visited, append 1.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Output matches postorder [3, 2, 1] [OK]
Hint: Postorder output for this tree is [3,2,1] [OK]
Common Mistakes:
  • Confusing order of appending nodes
  • Off-by-one in stack popping
2. You are given a binary tree where each node contains a non-negative integer value. You want to maximize the sum of values you can collect by selecting nodes such that no two directly connected nodes (parent-child) are both selected. Which approach guarantees an optimal solution for this problem?
easy
A. Use a greedy algorithm that always picks the node with the highest value first.
B. Use a depth-first search with dynamic programming that returns two values per node: max if robbing it and max if not robbing it.
C. Use a breadth-first search to select nodes level by level, picking the maximum values at alternate levels.
D. Use a brute force recursion that tries all subsets of nodes without any memoization.

Solution

  1. Step 1: Understand the problem constraints

    The problem requires selecting nodes in a tree such that no parent and child are both selected, maximizing the sum of selected nodes.
  2. Step 2: Identify the suitable algorithmic pattern

    A greedy or BFS level-based approach fails because the tree structure and adjacency constraints are complex. Brute force is correct but inefficient. The optimal solution uses DFS with DP returning two values per node: max if robbing it and max if not robbing it, ensuring all subproblems are solved optimally.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    DFS with two-value DP handles adjacency constraints correctly [OK]
Hint: Tree + no adjacent nodes -> DFS with two-value DP [OK]
Common Mistakes:
  • Assuming greedy or level-based selection works
  • Trying brute force without memoization
3. You are given a binary tree and need to determine if it is a mirror of itself (i.e., symmetric around its center). Which approach guarantees an optimal solution that efficiently checks this property by comparing nodes in a mirrored fashion?
easy
A. Use a recursive DFS that simultaneously compares the left subtree of one node with the right subtree of the other node, returning false immediately on mismatch.
B. Perform a level-order traversal and compare nodes at each level from left to right.
C. Traverse the tree in preorder and check if the sequence of node values is a palindrome.
D. Use a brute force approach that generates all subtree permutations and checks for symmetry.

Solution

  1. Step 1: Understand the problem requires mirrored subtree comparison

    The problem asks if the tree is symmetric, meaning the left subtree is a mirror reflection of the right subtree.
  2. Step 2: Identify the approach that compares mirrored nodes recursively with early exit

    The recursive DFS approach compares left subtree nodes with right subtree nodes in mirrored positions and returns false immediately if any mismatch is found, ensuring efficiency.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Mirrored recursive DFS matches problem requirements [OK]
Hint: Symmetry requires mirrored subtree comparison [OK]
Common Mistakes:
  • Assuming preorder traversal palindrome check works
  • Using level-order traversal without mirrored comparison
  • Trying brute force subtree permutations
4. The following BFS-based code attempts to compute the maximum depth of a binary tree. Identify the line containing the subtle bug that causes incorrect depth calculation for an empty tree input.
from collections import deque

def maxDepth(root):
    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
medium
A. Line 7: Using len(queue) to determine level size
B. Line 15: Incrementing depth after processing each level
C. Line 10: Popping node from queue without null check
D. Line 2: Initializing queue with root without checking if root is null

Solution

  1. Step 1: Check handling of empty tree

    Code initializes queue with root without checking if root is null, so if root is null, queue contains null, causing errors.
  2. Step 2: Verify other lines

    len(queue) and popping nodes are correct if queue is valid; depth increment is necessary after each level.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Missing root null check causes failure on empty tree [OK]
Hint: Always check for null root before queue initialization [OK]
Common Mistakes:
  • Not handling empty tree input
  • Assuming root always exists
  • Incrementing depth incorrectly
5. Suppose you want to invert a binary tree where nodes can have an arbitrary number of children (not just two). Which modification to the inversion algorithm correctly generalizes the inversion to this n-ary tree?
hard
A. Swap only the first and last child pointers recursively, leaving others unchanged.
B. Use BFS to swap children pairwise at each level without recursion.
C. Recursively invert each child's subtree, then reverse the list of children in-place.
D. Invert only the leftmost and rightmost subtrees recursively, ignoring middle children.

Solution

  1. Step 1: Understand inversion for binary tree swaps left and right children

    For n-ary trees, inversion means reversing the order of children after inverting each child's subtree.
  2. Step 2: Generalize recursion and reversal

    Recursively invert each child's subtree, then reverse the children list to mirror the tree structure.
  3. Step 3: Evaluate other options

    Swapping only first and last or partial BFS swaps do not fully invert the tree structure.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Recursion plus reversing children list generalizes inversion correctly [OK]
Hint: Invert subtrees recursively, then reverse children list for n-ary trees [OK]
Common Mistakes:
  • Swapping only some children pairs
  • Ignoring recursion on all children
  • Using BFS without recursion for full inversion
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