Practice
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
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 AQuick Check:
Count = (2^(3-1)-1) + left = 3 + 1 = 4 [OK]
- Off-by-one in binary search bounds
- Miscounting last level nodes
Solution
Step 1: Understand the problem requires the longest path between any two nodes, not necessarily passing through root.
The diameter can be found by checking the sum of left and right subtree heights at every node.Step 2: Recognize that a postorder traversal with recursion and a global variable to track diameter updates at each node ensures all paths are considered.
This approach visits each node once, updating the diameter with left_height + right_height.Final Answer:
Option A -> Option AQuick Check:
Postorder traversal with global diameter update covers all nodes [OK]
- Thinking diameter must pass through root
- Using greedy to pick deeper subtree only
- Confusing diameter with twice height
Solution
Step 1: Understand the problem constraints
The problem requires checking if any root-to-leaf path sums to the target. This naturally fits a tree traversal pattern.Step 2: Identify the best approach
DFS with early stopping is optimal because it explores paths deeply and stops as soon as a valid path is found, avoiding unnecessary work.Final Answer:
Option A -> Option AQuick Check:
DFS explores paths fully and stops early when possible [OK]
- Believing greedy approach works for sums
- Confusing BFS with DFS for path sums
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
