Practice
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)
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 BQuick Check:
Serialized string matches BFS with null markers trimmed correctly [OK]
- Including trailing null markers that should be trimmed
- Missing null markers for missing children
- Confusing order of nodes in BFS
Solution
Step 1: Identify auxiliary space usage in recursion
The algorithm uses recursion, so the call stack depth is proportional to the height h of the tree.Step 2: Distinguish between in-place operations and recursion stack
Swapping pointers is in-place (O(1) per node), but recursion stack space is O(h), not O(n).Final Answer:
Option D -> Option DQuick Check:
Recursion stack dominates space, proportional to tree height h [OK]
- Confusing in-place operation with O(1) total space
- Assuming queue-based BFS space applies to recursive DFS
- Counting node swaps as extra space
def lowestCommonAncestor(root, p, q):
parent = {root: None}
stack = [root]
while p not in parent or q not in parent:
node = stack.pop()
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
ancestors = set()
while p:
ancestors.add(p)
p = parent[p]
while q not in ancestors:
q = parent[q]
return q
Solution
Step 1: Analyze parent map construction loop
The loop 'while p not in parent or q not in parent:' ensures both nodes are in the parent map before ancestor sets are built.Step 2: Identify subtle bug
If one node is ancestor of the other, the loop may terminate prematurely if only one node is in parent map, causing KeyError later.Step 3: Explanation
The bug is that the loop condition does not guarantee both nodes are fully processed in the parent map before ancestor traversal.Final Answer:
Option A -> Option AQuick Check:
Loop condition must ensure both nodes are in parent map to avoid errors [OK]
- Assuming parent map always complete
- Ignoring incomplete parent map causing KeyError
- Misplacing bug in ancestor set loops
def pathSum(root, targetSum):
if not root:
return []
res = []
stack = [(root, [root.val], root.val)]
while stack:
node, path, current_sum = stack.pop()
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
Solution
Step 1: Identify condition for adding path to results
Correct code adds path only if current node is leaf and sum matches.Step 2: Locate bug
Here, path is added whenever sum matches, regardless of leaf status, causing incomplete paths to be included.Final Answer:
Option D -> Option DQuick Check:
Missing leaf check causes incorrect paths in results [OK]
- Adding path before confirming leaf node
- Forgetting to backtrack in recursion
Solution
Step 1: Understand traversal constraints
Without left/right pointers, standard Morris or recursion is not applicable; parent pointers only allow upward traversal.Step 2: Identify correct approach
Tracking previously visited nodes iteratively allows preorder traversal by moving up/down without extra space for recursion stack.Final Answer:
Option A -> Option AQuick Check:
Modified iterative approach handles parent-only trees without extra space [OK]
- Trying to use recursion without child pointers
- Attempting Morris traversal on parent pointers
- Using stack without tracking visited nodes
