Practice
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
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 CQuick Check:
Output matches postorder [3, 2, 1] [OK]
- Confusing order of appending nodes
- Off-by-one in stack popping
def maxPathSum(root):
max_sum = float('-inf')
def max_gain(node):
nonlocal max_sum
if not node:
return 0
left_gain = max_gain(node.left)
right_gain = max_gain(node.right)
current_path_sum = node.val + left_gain + right_gain
max_sum = max(max_sum, current_path_sum)
# Bug: returns sum of both left and right gains to parent
return node.val + left_gain + right_gain
max_gain(root)
return max_sum
Solution
Step 1: Understand return value meaning
The function returns the maximum gain from the current node to its parent, which must be a single path (not both children).Step 2: Identify the bug
Returning node.val + left_gain + right_gain sums both children, which is invalid for parent gain; only one child path can be extended.Final Answer:
Option D -> Option DQuick Check:
Return should be node.val + max(left_gain, right_gain) [OK]
- Returning sum of both children gains
- Ignoring negative gains
- Updating max_sum incorrectly
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 BQuick Check:
Correct inorder_index initialization is critical for stack popping logic [OK]
- Wrong inorder_index initialization
- Confusing postorder traversal direction
- Incorrect stack popping conditions
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
def dfs(node, curr_sum):
if not node:
return False
curr_sum += node.val
if curr_sum == targetSum: # Bug here
return True
return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
return dfs(root, 0)
Solution
Step 1: Understand leaf node condition
The sum should be checked only at leaf nodes, not at every node.Step 2: Identify the bug
Line 6 checks sum at any node, causing premature True returns for partial paths.Final Answer:
Option B -> Option BQuick Check:
Bug causes incorrect True if partial path sum equals targetSum [OK]
- Checking sum at internal nodes
- Not handling null root
Solution
Step 1: Understand impact of negative values
Negative values mean partial sums can decrease later, so pruning based on current sum is unsafe.Step 2: Adjust algorithm accordingly
Early stopping based on partial sums must be removed to avoid missing valid paths.Final Answer:
Option D -> Option DQuick Check:
Negative values break pruning assumptions, so early stopping must be disabled [OK]
- Assuming early stopping always works
- Switching to BFS unnecessarily
