BST Iterator (In-Order Next)

📋

BST Iterator (In-Order Next)

Edge cases:

</>

IDE

class BSTIterator: def __init__(self, root: Optional[TreeNode]):public class BSTIterator { public BSTIterator(TreeNode root) {class BSTIterator { public: BSTIterator(TreeNode* root) {class BSTIterator { constructor(root) {

class BSTIterator:
    def __init__(self, root):
        # Write your solution here
        pass
    def next(self):
        pass
    def hasNext(self):
        pass

class BSTIterator {
    public BSTIterator(TreeNode root) {
        // Write your solution here
    }
    public int next() {
        return 0;
    }
    public boolean hasNext() {
        return false;
    }
}

class BSTIterator {
public:
    BSTIterator(TreeNode* root) {
        // Write your solution here
    }
    int next() {
        return 0;
    }
    bool hasNext() {
        return false;
    }
};

class BSTIterator {
    constructor(root) {
        // Write your solution here
    }
    next() {
        return 0;
    }
    hasNext() {
        return false;
    }
}

Common Bugs to Avoid

Wrong: next() returns nodes out of ascending orderIncorrect traversal order or stack not maintained properly.✅ Use a stack to simulate controlled inorder traversal, pushing leftmost nodes and updating after next().

Wrong: hasNext() returns false prematurely or remains true after last elementStack state not updated correctly after next(), or hasNext() logic incorrect.✅ Check stack emptiness for hasNext(); update stack after popping node in next().

Wrong: Repeated nodes returned or nodes skippedConfusing 0/1 visit with unbounded visits; pushing nodes multiple times.✅ Push leftmost path of right child only once after popping current node; do not revisit nodes.

Wrong: Repeated hasNext() calls advance iterator or change outputhasNext() modifies iterator state incorrectly.✅ Ensure hasNext() only checks stack state without popping or pushing nodes.

Wrong: Solution times out on large inputFull traversal preprocessing or O(n) per call approach used.✅ Implement controlled inorder traversal using stack with O(h) space and average O(1) time per call.

✓

Test Cases

Try testing your iterator on minimal and skewed trees to catch base case bugs.

Focus on algorithmic correctness: no repeated visits, no greedy shortcuts.

Optimize your solution to use O(h) space and average O(1) time per call.

t1_01basic

Input{"root":[7,3,15,null,null,9,20],"calls":["next","next","hasNext","next","hasNext","next","hasNext","next","hasNext"]}

Expected[3,7,true,9,true,15,true,20,false]

⏱ Performance - must finish in 2000ms

The BST in-order traversal is [3,7,9,15,20]. Each next() call returns the next smallest element. hasNext() checks if more elements remain.

💡 Recall that in-order traversal of BST yields sorted order.

💡 Use a controlled stack-based traversal to yield next smallest efficiently.

💡 Initialize stack with leftmost path; next() pops and pushes right child's leftmost path.

Why it failed: Returned values do not follow in-order sequence or hasNext() is incorrect. Fix by maintaining a stack of nodes representing the next smallest elements and updating it correctly after each next() call.

✓ Correct in-order iteration with proper hasNext() checks.

t1_02basic

Input{"root":[5,1,7,0,2,null,8],"calls":["hasNext","next","next","hasNext","next","next","next","hasNext"]}

Expected[true,0,1,true,2,5,7,true]

⏱ Performance - must finish in 2000ms

In-order traversal is [0,1,2,5,7,8]. Calls return next smallest values and hasNext() status accordingly.

💡 Check that hasNext() returns true before any next() calls if tree is non-empty.

💡 Ensure next() returns nodes in ascending order.

💡 Maintain stack state correctly after each next() to reflect remaining nodes.

Why it failed: Incorrect next() values or hasNext() status indicates stack not updated properly after next(). Fix by pushing leftmost nodes of right subtree after popping.

✓ Iterator correctly returns next smallest and updates hasNext() status.

t2_01edge

Input{"root":[42],"calls":["hasNext","next","hasNext"]}

Expected[true,42,false]

⏱ Performance - must finish in 2000ms

Single node tree: next() returns the only node, hasNext() false afterwards.

💡 Test behavior on minimal tree with one node.

💡 Ensure hasNext() is true before first next(), false after last.

💡 Stack should initialize with root only and empty after next().

Why it failed: Fails single node case if hasNext() remains true after last element or next() returns wrong value. Fix by popping last node and updating stack accordingly.

✓ Handles single node tree correctly.

t2_02edge

Input{"root":[5,4,null,3,null,2,null,1],"calls":["next","next","next","next","next","hasNext"]}

Expected[1,2,3,4,5,false]

⏱ Performance - must finish in 2000ms

Left skewed tree: iterator returns nodes in ascending order (reverse of insertion order).

💡 Left skewed tree means all nodes have only left child.

💡 Stack initialization must push all left children down to leaf.

💡 Each next() pops top and pushes right child's leftmost path (none here).

Why it failed: If output is not sorted ascending or hasNext() is incorrect, stack initialization or update is wrong. Fix by pushing all left nodes initially and after next().

✓ Correctly iterates left skewed tree in ascending order.

t2_03edge

Input{"root":[1,null,2,null,3,null,4,null,5],"calls":["next","next","next","next","next","hasNext"]}

Expected[1,2,3,4,5,false]

⏱ Performance - must finish in 2000ms

Right skewed tree: iterator returns nodes in ascending order (same as insertion order).

💡 Right skewed tree means all nodes have only right child.

💡 Stack initially contains only root; after next(), push right child's leftmost path.

💡 Check that hasNext() is false after last element.

Why it failed: If next() returns wrong order or hasNext() remains true after last element, stack update logic is flawed. Fix by pushing leftmost path of right child after next().

✓ Correctly iterates right skewed tree in ascending order.

t2_04edge

Input{"root":[10],"calls":["hasNext","hasNext","next","hasNext","hasNext"]}

Expected[true,true,10,false,false]

⏱ Performance - must finish in 2000ms

Repeated calls to hasNext() without next() should not advance iterator or change output.

💡 hasNext() must be idempotent and not modify iterator state.

💡 Only next() advances the pointer and stack.

💡 Check that repeated hasNext() calls return consistent results.

Why it failed: If repeated hasNext() calls advance iterator or change output, fix by separating state changes to next() only.

✓ hasNext() calls do not advance iterator; next() advances correctly.

t3_01corner

Input{"root":[10,5,15,3,7,null,18],"calls":["next","next","next","next","next","next","next","hasNext"]}

Expected[3,5,7,10,15,18,20,false]

⏱ Performance - must finish in 2000ms

Greedy trap test: next() must return nodes in ascending order, not just leftmost or largest child.

💡 Beware of greedy approaches that always pick leftmost or largest child without stack.

💡 Use controlled stack to track next smallest node correctly.

💡 Push leftmost path of right child after popping current node.

Why it failed: Greedy approach returns incorrect next() values or null prematurely. Fix by maintaining stack of nodes representing next smallest candidates.

✓ Iterator correctly returns next smallest nodes in order.

t3_02corner

Input{"root":[8,3,10,1,6,null,14,null,null,4,7,13],"calls":["next","next","hasNext","next","next","next","hasNext","next","next","hasNext"]}

Expected[1,3,true,4,6,7,true,8,10,true]

⏱ Performance - must finish in 2000ms

0/1 vs unbounded confusion test: each node visited exactly once; no duplicates or repeated visits.

💡 Ensure each node is returned exactly once, no repeats.

💡 Stack must not re-push nodes already visited.

💡 After next(), push leftmost path of right child only once.

Why it failed: If nodes repeat or are skipped, iterator confuses 0/1 visit with unbounded. Fix by careful stack push/pop logic to visit each node once.

✓ Iterator visits each node exactly once in ascending order.

t3_03corner

Input{"root":[20,10,30,5,15,25,35],"calls":["hasNext","hasNext","next","next","hasNext","next","hasNext","next","hasNext","next","hasNext","next","hasNext"]}

Expected[true,true,5,10,true,15,true,20,true,25,true,30,true]

⏱ Performance - must finish in 2000ms

Repeated hasNext() calls without next() should not advance iterator or change output.

💡 hasNext() must be idempotent and not modify iterator state.

💡 Only next() advances the pointer and stack.

💡 Check that repeated hasNext() calls return consistent results.

Why it failed: If repeated hasNext() calls advance iterator or change output, fix by separating state changes to next() only.

✓ hasNext() calls do not advance iterator; next() advances correctly.

t4_01performance

Input{"root":[50000,25000,75000,12500,37500,62500,87500,6250,18750,31250,43750,56250,68750,81250,93750,3125,9375,15625,21875,28125,34375,40625,46875,53125,59375,65625,71875,78125,84375,90625,96875],"calls":["hasNext","next","hasNext","next","hasNext","next","hasNext","next","hasNext","next","hasNext","next","hasNext","next","hasNext","next","hasNext","next","hasNext","next"]}

Expectednull

⏱ Performance - must finish in 2000ms

Large balanced BST with 31 nodes (simulated here for brevity) and 20 calls to next() and hasNext(). Must complete in O(h) average time per call.

💡 Use controlled inorder traversal with stack of height h.

💡 Avoid full traversal preprocessing to save memory and time.

💡 Average O(1) time per next()/hasNext() call is required.

Why it failed: Brute force or full traversal preprocessing causes TLE due to O(n) per call or O(n) memory. Fix by using stack-based lazy traversal with O(h) space and average O(1) time.

✓ Efficient stack-based iterator passes performance constraints.

Practice

1. You are given a binary search tree (BST) and need to transform it so that every node's new value is the sum of all node values greater than or equal to it in the original BST. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Perform an inorder traversal to collect nodes, then for each node sum all greater nodes' values in a separate pass.

B. Use a breadth-first search (BFS) to visit nodes level by level and update values based on a global sum.

C. Traverse the BST in reverse inorder (right-root-left) while accumulating a running sum and update nodes on the fly.

D. Apply a postorder traversal (left-right-root) and update each node after processing its children.

Solution

1. Step 1: Understand the problem requirement

   The problem requires updating each node's value to include all greater or equal values, which naturally aligns with processing nodes from largest to smallest.

2. Step 2: Identify traversal order that processes nodes from largest to smallest

   Reverse inorder traversal (right-root-left) visits nodes in descending order, allowing accumulation of sums as we go.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Reverse inorder traversal accumulates sums correctly [OK]

Hint: Reverse inorder traversal processes nodes descending [OK]

Common Mistakes:

• Using inorder traversal processes smaller nodes first, causing incorrect sums
• Using BFS does not guarantee order by node value
• Postorder traversal processes children before root, not suitable here

2. You are given a sorted array of unique integers and need to construct a binary search tree with minimal height. Which approach guarantees the resulting tree is height-balanced and constructed in O(n) time?

easy

A. Use a divide-and-conquer recursion that picks the middle element as root and recursively builds left and right subtrees.

B. Insert elements one by one into an empty BST using standard BST insertion.

C. Use a greedy approach that always inserts the smallest remaining element as the left child.

D. Build a balanced BST by repeatedly merging two smaller balanced BSTs.

Solution

1. Step 1: Understand the problem constraints

   The input is a sorted array, and the goal is to build a height-balanced BST efficiently.

2. Step 2: Evaluate approaches

   Inserting elements one by one leads to skewed trees and O(n^2) time. Greedy insertion of smallest elements does not guarantee balance. Merging BSTs is not straightforward and inefficient. The divide-and-conquer approach picks the middle element as root, ensuring balanced subtrees and O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Middle element chosen recursively -> balanced BST in O(n) time [OK]

Hint: Middle element recursion ensures balanced BST [OK]

Common Mistakes:

• Thinking inserting one by one is efficient
• Assuming greedy insertion balances tree

3. Consider the following Python code implementing the Morris inorder traversal to recover a BST with two swapped nodes. Given the input tree with nodes [3,1,4,null,null,2] where nodes 2 and 3 are swapped, what is the value of the variable second.val after the traversal completes?

easy

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Trace inorder traversal with Morris method

   The inorder traversal visits nodes in order: 1, 3, 2, 4. The violations are detected when prev.val > current.val: first at (3,2).

2. Step 2: Identify swapped nodes

   First violation sets first=3, second=2. No second violation occurs, so second remains 2.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Second node detected is the node with value 2 [OK]

Hint: Second swapped node is the smaller value in violation [OK]

Common Mistakes:

• Confusing first and second nodes
• Missing second violation for adjacent swaps
• Off-by-one in traversal order

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

A. O(H + k), where H is the height of the tree and k is the kth element to find

B. O(k), since only k nodes are visited

C. O(k log n), assuming balanced BST

D. O(n), where n is the total number of nodes in the BST

Solution

1. Step 1: Analyze traversal steps

   The algorithm traverses down to the leftmost node (cost O(H)) and then visits k nodes in inorder sequence.

2. Step 2: Combine costs

   Total time is O(H) to reach leftmost node plus O(k) to visit k nodes, so O(H + k).

3. Final Answer:

   Option A -> Option A

4. Quick 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. The following code attempts to find if there exist two distinct nodes in a BST whose values sum to k. Identify the line containing the subtle bug that can cause incorrect results.

medium

A. Line 6: dfs(node.left)

B. Line 4: if k - node.val in seen:

C. Line 7: seen.add(node.val)

D. Line 8: dfs(node.right)

Solution

1. Step 1: Understand DFS and set usage

   The code checks if complement exists in seen before adding current node's value.

2. Step 2: Identify bug in order of operations

   Checking complement before adding current node's value misses pairs where both nodes are the same, or misses valid pairs if current node's value is needed for complement checks in children.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Complement check must happen after adding current node's value to seen [OK]

Hint: Add current node to set before checking complements [OK]

Common Mistakes:

• Checking complement before adding current node's value
• Not handling None nodes properly
• Returning False too early