The algorithm begins by calling dfs on the root node (value 5) with an initial current sum of 0.
💡 This initializes the recursion and sets the starting point for accumulating sums along paths.
Line:return dfs(root, 0)
💡 The root node is the entry point for the DFS traversal.
fill_cells
Add node 5's value to current sum
At node 5, add its value (5) to the current sum (0), updating current sum to 5.
💡 Updating the sum is essential to track the path's total as we go deeper.
Line:curr_sum += node.val
💡 The current sum now reflects the path sum from root to this node.
traverse
Recurse into left child node 4
The algorithm calls dfs on node 4 (left child of 5) with current sum 5.
💡 Exploring left subtree first follows DFS order and accumulates sums along this path.
Line:return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
💡 The recursion stack grows as we go deeper into the left subtree.
fill_cells
Add node 4's value to current sum
At node 4, add its value (4) to current sum (5), updating current sum to 9.
💡 Updating the sum continues to track the total along the current path.
Line:curr_sum += node.val
💡 The sum now reflects the path 5->4.
traverse
Recurse into left child node 11
The algorithm calls dfs on node 11 (left child of 4) with current sum 9.
💡 Continuing down the left subtree to explore deeper paths.
Line:return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
💡 The recursion stack deepens as we explore this path.
fill_cells
Add node 11's value to current sum
At node 11, add its value (11) to current sum (9), updating current sum to 20.
💡 Sum accumulation continues as we go deeper into the path.
Line:curr_sum += node.val
💡 The sum now reflects the path 5->4->11.
traverse
Recurse into left child node 7 (leaf)
The algorithm calls dfs on node 7 (left child of 11) with current sum 20.
💡 Exploring the left leaf node to check if path sum matches target.
Line:return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
💡 We are now at a leaf node candidate for path sum check.
compare
Add node 7's value to current sum and check leaf condition
At leaf node 7, add its value (7) to current sum (20), total 27. Check if 27 equals target 22; it does not.
💡 Leaf nodes are where we check if the path sum matches the target.
Line:if not node.left and not node.right:
return curr_sum == targetSum
💡 This path does not satisfy the target sum condition.
traverse
Backtrack and recurse into right child node 2
Since left leaf path failed, backtrack to node 11 and recurse into its right child node 2 with current sum 20.
💡 Backtracking allows exploring alternative paths when one fails.
Line:return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
💡 The algorithm explores all possible paths until one matches the target sum.
compare
Add node 2's value to current sum and check leaf condition
At leaf node 2, add its value (2) to current sum (20), total 22. Check if 22 equals target 22; it does.
💡 Finding a leaf node where the path sum matches the target means success.
Line:if not node.left and not node.right:
return curr_sum == targetSum
💡 The algorithm finds a valid path and returns True immediately.
returning
Return True up the call stack to root
The True result propagates back through the call stack, returning True at each level without exploring other branches.
💡 Early stopping avoids unnecessary exploration once a valid path is found.
Line:return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
💡 The algorithm efficiently stops searching after success.
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
def dfs(node, curr_sum):
if not node:
return False # STEP 1: Null node returns False
curr_sum += node.val # STEP 2: Add node value to current sum
if not node.left and not node.right: # STEP 3: Check leaf node
return curr_sum == targetSum # STEP 4: Return True if sum matches
# STEP 5: Recurse left subtree
left_result = dfs(node.left, curr_sum)
if left_result:
return True # STEP 6: Early return if left subtree has path
# STEP 7: Recurse right subtree
right_result = dfs(node.right, curr_sum)
return right_result # STEP 8: Return right subtree result
return dfs(root, 0) # STEP 9: Start DFS from root with sum 0
📊
Path Sum - Watch the Algorithm Execute, Step by Step
Watching the algorithm step through each node and decision reveals how early stopping works and how the recursion stack evolves, making the path sum logic crystal clear.
✓ DFS explores each root-to-leaf path accumulating sums to check for target sum.
This insight is hard to see from code alone because recursion hides the path exploration order.
✓ Early stopping returns true immediately when a valid path is found, avoiding unnecessary work.
Visualizing the call stack and return values clarifies how early stopping improves efficiency.
✓ Backtracking occurs when a path fails, and the algorithm explores alternative branches systematically.
Seeing the recursion unwind and try other branches concretely shows how all paths are checked.
Practice
(1/5)
1. Consider the following code snippet implementing the optimal countNodes function for a complete binary tree. Given the tree:
1
/ \
2 3
/
4
What is the final return value of countNodes(root)?
easy
A. 4
B. 3
C. 5
D. 6
Solution
Step 1: Calculate tree height
Height h = 3 (nodes 1 -> 2 -> 4).
Step 2: Binary search on last level nodes
Last level has indices 0 to 3. Check existence:
- idx=0 exists (node 4)
- idx=1 does not exist
So left ends at 1.
Final Answer:
Option A -> Option A
Quick Check:
Count = (2^(3-1)-1) + left = 3 + 1 = 4 [OK]
Hint: Count = perfect nodes + last level nodes found [OK]
Common Mistakes:
Off-by-one in binary search bounds
Miscounting last level nodes
2. Given the following code snippet for serialization using BFS, what is the serialized string output for the binary tree below?
Tree:
1
/ \
2 3
/ \
4 null
from collections import deque
def serialize(root):
if not root:
return ''
queue = deque([root])
vals = []
while queue:
node = queue.popleft()
if node:
vals.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
else:
vals.append('X')
while vals and vals[-1] == 'X':
vals.pop()
return ','.join(vals)
easy
A. 1,2,3,4,X,X,X
B. 1,2,3,X,X,4
C. 1,2,3,X,X,4,X,X,X
D. 1,2,3,X,X,4,X
Solution
Step 1: Trace queue processing
Start with queue=[1]. Pop 1, append '1', enqueue 2 and 3. Queue=[2,3].
Step 2: Continue BFS and record values
Pop 2, append '2', enqueue left and right (both null) -> enqueue X,X. Pop 3, append '3', enqueue 4 and null -> enqueue 4,X. Pop nulls append 'X'. Remove trailing 'X's at end.
Final Answer:
Option B -> Option B
Quick Check:
Serialized string matches BFS with null markers trimmed correctly [OK]
Hint: Trailing 'X's are removed after BFS serialization [OK]
Common Mistakes:
Including trailing null markers that should be trimmed
Missing null markers for missing children
Confusing order of nodes in BFS
3. What is the time complexity of the optimal iterative postorder traversal algorithm for computing the maximum path sum in a binary tree with n nodes and height h?
medium
A. O(n) because each node is visited a constant number of times
B. O(n log n) due to repeated subtree computations
C. O(h * n) because the stack operations depend on tree height
D. O(n^2) in worst case due to nested traversal of subtrees
Solution
Step 1: Identify node visits
Each node is pushed and popped from the stack once, and gains are computed once per node.
Step 2: Analyze stack operations and computations
Stack size is at most h, but operations per node are constant, so total time is proportional to n.
Final Answer:
Option A -> Option A
Quick Check:
Linear time traversal with constant work per node [OK]
4. Consider the following buggy code snippet for building a tree from inorder and postorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or runtime errors?
medium
A. Line creating root node with postorder[-1]
B. Line initializing inorder_index to 0
C. Line attaching node as right child
D. Line popping from stack inside while loop
Solution
Step 1: Identify inorder_index initialization
inorder_index should start at the last index (len(inorder) - 1) because postorder is processed from end to start.
Step 2: Consequences of wrong initialization
Starting at 0 causes incorrect comparisons and popping logic, leading to wrong tree structure or runtime errors.
Final Answer:
Option B -> Option B
Quick Check:
Correct inorder_index initialization is critical for stack popping logic [OK]
Hint: inorder_index must start at last index, not zero [OK]
Common Mistakes:
Wrong inorder_index initialization
Confusing postorder traversal direction
Incorrect stack popping conditions
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.