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.
💡 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.
💡 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.
✓ 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
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.
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.
Final Answer:
Option C -> Option C
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
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.
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.
Final Answer:
Option B -> Option B
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
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.
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.
Final Answer:
Option A -> Option A
Quick Check:
Mirrored recursive DFS matches problem requirements [OK]
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
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.
Step 2: Verify other lines
len(queue) and popping nodes are correct if queue is valid; depth increment is necessary after each level.
Final Answer:
Option D -> Option D
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
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.
Step 2: Generalize recursion and reversal
Recursively invert each child's subtree, then reverse the children list to mirror the tree structure.
Step 3: Evaluate other options
Swapping only first and last or partial BFS swaps do not fully invert the tree structure.
Final Answer:
Option C -> Option C
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 unknownstrongwhile earning +1 Grip toward your certificate.