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
depth after the second iteration of the while loop?
Tree structure:
- Root node 1
- Left child 2
- Right child 3
- Left child of 2 is 4
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root):
if root is None:
return 0
queue = deque([root])
depth = 0
while queue:
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
depth += 1
return depth
root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
print(maxDepth(root))
Solution
Step 1: Trace first iteration of while loop
Initially, queue contains root (1). level_size=1. After processing node 1, enqueue its children 2 and 3. Increment depth to 1.Step 2: Trace second iteration of while loop
Queue now has nodes 2 and 3. level_size=2. Process node 2 (enqueue 4), process node 3 (no children). Increment depth to 2.Final Answer:
Option B -> Option BQuick Check:
Depth increments after each level processed; after second level depth=2 [OK]
- Counting nodes instead of levels
- Off-by-one in depth increment
- Ignoring children enqueueing
Solution
Step 1: Understand the impact of duplicates
Duplicates break the uniqueness of value-to-index mapping in inorder traversal, so a simple hash map is insufficient.Step 2: Required modification
Store all indices of each value in inorder and track which occurrence is used to correctly split subtrees and avoid ambiguity.Step 3: Why other options fail
Ignoring duplicates or switching traversals does not solve ambiguity; greedy approach fails to reconstruct correct structure.Final Answer:
Option A -> Option AQuick Check:
Tracking multiple indices per value is necessary for duplicates [OK]
- Ignoring duplicates in hash map
- Assuming unique values always
- Switching traversal types incorrectly
Solution
Step 1: Recognize diameter depends on path length (edges), not node values.
Negative values do not affect height or path length calculations.Step 2: Confirm standard height-based diameter algorithm works unchanged.
Heights and diameter calculations rely on structure, so no changes are needed.Final Answer:
Option A -> Option AQuick Check:
Diameter depends on edges, not node values [OK]
- Confusing diameter with max sum path
- Ignoring negative nodes incorrectly
- Switching to BFS unnecessarily
