Practice
Solution
Step 1: Understand traversal order requirement
Inorder traversal visits left subtree, then node, then right subtree, matching the problem's order.Step 2: Identify approach with O(1) space
Morris traversal achieves inorder traversal without recursion or stack by temporarily modifying tree pointers, restoring them after use.Final Answer:
Option C -> Option CQuick Check:
Morris traversal is known for O(1) space inorder traversal [OK]
- Confusing preorder with inorder traversal order
- Assuming BFS can produce inorder sequence
- Thinking DP applies to traversal order
Solution
Step 1: Understand traversal order requirement
The problem requires visiting root before left and right subtrees, which is preorder traversal.Step 2: Identify approach with no extra space
Morris preorder traversal uses threaded binary trees to achieve preorder traversal without recursion or stack, thus optimal in space.Final Answer:
Option C -> Option CQuick Check:
Preorder visits root first; Morris traversal achieves this with O(1) space [OK]
- Confusing inorder or postorder with preorder traversal
- Assuming recursion is always needed
- Using level-order which visits nodes by depth
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
def dfs(node, curr_sum):
if not node:
return False
curr_sum += node.val
if not node.left and not node.right:
return curr_sum == targetSum
return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
return dfs(root, 0)
Solution
Step 1: Trace the path sums
Check root-to-leaf paths: - 5↔4↔11↔7 = 27 - 5↔4↔11↔2 = 22 (matches targetSum) - 5↔8↔13 = 26 - 5↔8↔4↔1 = 18 Since one path sums to 22, the function returns True.Step 2: Confirm code logic
The DFS returns True as soon as it finds the matching path sum at a leaf node.Final Answer:
Option A -> Option AQuick Check:
Path 5↔4↔11↔2 sums to 22, so return True [OK]
- Stopping at non-leaf nodes
- Ignoring leaf node condition
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 AQuick Check:
Linear time traversal with constant work per node [OK]
- Confusing stack height with repeated visits
- Assuming nested loops cause O(n^2)
- Thinking recursion stack adds multiplicative factor
Solution
Step 1: Understand diameter definition counts edges, not nodes.
The diameter is the number of edges on the longest path, so it should be left + right, not left + right + 1.Step 2: Identify the bug line.
Line 9 adds 1 incorrectly, causing diameter to be off by one.Final Answer:
Option B -> Option BQuick Check:
Diameter must be sum of left and right heights (edges), not nodes [OK]
- Adding 1 to diameter sum
- Not using nonlocal for diameter
- Returning wrong height value
