Practice
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: Analyze height computation calls
Height is computed recursively for each node, and each height call traverses subtree nodes.Step 2: Calculate total calls
For n nodes, height is called at each node, and each call can take O(n) in worst case, leading to O(n^2) total time.Final Answer:
Option A -> Option AQuick Check:
Repeated height calls cause quadratic time [OK]
- Assuming height calls are O(1) leading to O(n) time
- Confusing height with depth or tree height h
- Thinking O(n log n) due to balanced tree assumption
def inorderTraversal(root):
result = []
current = root
while current:
if not current.left:
result.append(current.val)
current = current.right
else:
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if not predecessor.right:
predecessor.right = current # create thread
current = current.left
else:
# BUG: missing line to remove thread
result.append(current.val)
current = current.right
return result
Solution
Step 1: Identify thread removal step
Morris traversal requires removing the temporary thread by setting predecessor.right = None after visiting the node.Step 2: Locate missing removal
The code lacks the line resetting predecessor.right = None, causing infinite loops or corrupted tree structure.Final Answer:
Option A -> Option AQuick Check:
Without removing thread, traversal loops endlessly [OK]
- Forgetting to remove thread
- Appending node before removing thread
- Incorrectly creating thread
Solution
Step 1: Analyze time complexity
Using a hash map avoids repeated linear searches, so each node is processed once -> O(n) time.Step 2: Analyze space complexity
Hash map stores n elements, recursion stack can be up to O(n) in skewed trees, so total auxiliary space is O(n).Final Answer:
Option A -> Option AQuick Check:
Time is O(n), space includes recursion stack and hash map [OK]
- Assuming slicing causes O(n^2) time
- Ignoring recursion stack space
- Confusing balanced tree depth with complexity
Solution
Step 1: Review rewiring steps
The code sets root.right = prev but does not set root.left = None, so left pointers remain.Step 2: Identify missing step
Setting root.left = None is required to ensure the flattened list has no left children.Final Answer:
Option A -> Option AQuick Check:
Left pointers must be nullified to meet problem constraints [OK]
- Forgetting to nullify left pointers
- Misordering recursive calls causing wrong sequence
- Losing subtree references by incorrect rewiring
