Recommended
Practice
1. Given the following code snippet for converting a sorted array to a height-balanced BST, what is the value of the root node's value after the first call to
helper with input nums = [1, 3, 5]?easy
Solution
Step 1: Calculate mid index for initial call
For nums=[1,3,5], left=0, right=2, mid=(0+2)//2=1.Step 2: Identify root value
nums[mid] = nums[1] = 3, so root node value is 3.Final Answer:
Option A -> Option AQuick Check:
Mid index calculation picks 3 as root [OK]
Hint: Mid index picks middle element as root [OK]
Common Mistakes:
- Choosing first or last element as root
- Off-by-one mid calculation
2. Consider the following code for computing the range sum of a BST. Given the BST with root value 10, left child 5, right child 15, and range [7, 15], what is the final value of
total returned by rangeSumBST?easy
Solution
Step 1: Trace initial stack and total
Start with stack=[10], total=0.Step 2: Pop 10 (in range), add 10, push left(5) and right(15)
total=10, stack=[5,15]Step 3: Pop 15 (in range), add 15, push left(null) and right(null)
total=25, stack=[5,null,null]Step 4: Pop null (skip), then pop null (skip), then pop 5 (less than low=7), push right(null)
total=25, stack=[null]Step 5: Pop null (skip), stack empty, return total=25
5 is less than low, so it is skipped and not added.Final Answer:
Option A -> Option AQuick Check:
Sum includes 10 and 15 only, total=25 [OK]
Hint: Only nodes within [7,15] add to total [OK]
Common Mistakes:
- Adding nodes outside range
- Forgetting to push children after adding node
3. The following code attempts to implement a BST Iterator using the Morris traversal technique. Identify the bug that can cause the tree structure to remain corrupted after iteration.
class BSTIterator:
def __init__(self, root):
self.current = root
self.next_val = None
self._advance()
def _advance(self):
while self.current:
if not self.current.left:
self.next_val = self.current.val
self.current = self.current.right
return
else:
pre = self.current.left
while pre.right and pre.right != self.current:
pre = pre.right
if not pre.right:
pre.right = self.current
self.current = self.current.left
else:
# BUG: Missing restoration of thread
self.next_val = self.current.val
self.current = self.current.right
medium
Solution
Step 1: Identify thread restoration step
In Morris traversal, after visiting a node, the temporary thread (pre.right) must be reset to null to restore the tree.Step 2: Locate missing restoration
The code omits resetting pre.right = None in the else block, causing the tree to remain modified after iteration.Final Answer:
Option A -> Option AQuick Check:
Missing thread removal corrupts tree structure [OK]
Hint: Always restore threads to avoid tree corruption [OK]
Common Mistakes:
- Forgetting to remove threads
- Misplacing next_val assignment
- Incorrect current pointer updates
4. What is the time complexity of the iterative inorder traversal approach to find the kth smallest element in a BST, where H is the height of the tree and k is the input parameter?
medium
Solution
Step 1: Analyze traversal steps
The algorithm traverses down to the leftmost node (cost O(H)) and then visits k nodes in inorder sequence.Step 2: Combine costs
Total time is O(H) to reach leftmost node plus O(k) to visit k nodes, so O(H + k).Final Answer:
Option A -> Option AQuick Check:
Traversal cost depends on height plus k nodes visited [OK]
Hint: Traversal cost includes height plus k nodes visited [OK]
Common Mistakes:
- Assuming O(n) always
- Ignoring height cost
- Assuming only k nodes visited without stack overhead
5. Suppose the problem is extended so that multiple pairs of nodes (more than two nodes) are swapped in the BST, possibly non-adjacent. Which of the following modifications to the recovery algorithm is correct and efficient?
hard
Solution
Step 1: Understand the problem extension
Multiple pairs of nodes swapped means multiple violations, possibly complex to detect and fix in one pass.Step 2: Evaluate approaches
Morris traversal detects only two nodes swapped optimally; multiple swaps require collecting all values, sorting, and rewriting nodes, which brute force does efficiently.Final Answer:
Option C -> Option CQuick Check:
Brute force approach handles multiple swaps correctly by sorting all values [OK]
Hint: Multiple swaps require full value sorting and rewriting [OK]
Common Mistakes:
- Assuming Morris traversal can fix multiple swaps in one pass
- Trying to swap nodes immediately without full detection
- Running multiple passes of Morris traversal inefficiently