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 tree where exactly two nodes have been swapped by mistake, violating the binary search tree property. Which approach guarantees an optimal solution to recover the tree without changing its structure or using extra space beyond a constant amount?

easy

A. Use a bottom-up dynamic programming approach to reconstruct the BST by comparing subtrees and swapping nodes.

B. Perform an inorder traversal, store values in a list, sort the list, then overwrite the tree nodes with sorted values.

C. Apply a greedy approach by swapping any two nodes that violate the BST property during a single inorder traversal pass.

D. Use Morris inorder traversal to detect the two swapped nodes during traversal and swap their values, achieving O(1) space complexity.

Solution

1. Step 1: Understand the problem constraints

   The problem requires recovering a BST where two nodes are swapped, without extra space and without changing the tree structure.

2. Step 2: Identify the approach that meets constraints

   Morris inorder traversal allows inorder traversal without recursion or stack, detecting swapped nodes on the fly and swapping their values, achieving O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Morris traversal is the only approach with O(1) space and no structural changes [OK]

Hint: Morris traversal enables O(1) space recovery [OK]

Common Mistakes:

• Assuming sorting values is optimal despite extra space
• Believing greedy single pass fixes all cases
• Confusing DP with tree recovery

2. Consider the following Python code implementing BST validation using inorder traversal. What is the output of the program when run with the given test cases?

easy

A. true followed by false

B. true followed by true

C. false followed by true

D. false followed by false

Solution

1. Step 1: Trace first tree (2,1,3)

   Inorder traversal yields [1,2,3], strictly increasing, so returns true.

2. Step 2: Trace second tree (5,1,4 with children 3 and 6)

   Inorder traversal yields [1,5,3,4,6], 3 < 5 violates BST property, so returns false.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First tree valid BST, second invalid due to subtree violation [OK]

Hint: Inorder traversal must be strictly increasing [OK]

Common Mistakes:

• Assuming subtree root comparison is enough
• Confusing output order
• Missing strict inequality check

3. What is the time complexity of balancing a BST using the optimal approach of inorder traversal followed by iterative balanced BST construction from the collected nodes?

medium

A. O(n log n) due to sorting nodes during traversal

B. O(n) because inorder traversal and balanced rebuild each take linear time

C. O(n^2) because rebuilding the tree involves repeated subtree constructions

D. O(n) for traversal but O(n log n) for balanced tree construction

Solution

1. Step 1: Analyze inorder traversal time

   Inorder traversal visits each node once -> O(n).

2. Step 2: Analyze balanced BST construction time

   Rebuilding uses indices to pick middle nodes without extra sorting -> O(n).

3. Step 3: Consider sorting complexity

   Although inorder traversal produces sorted nodes, if sorting is mistakenly applied, complexity becomes O(n log n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting nodes during traversal leads to O(n log n) [Trap]

Hint: Beware of sorting overhead; if sorting is done, complexity is O(n log n)

Common Mistakes:

• Assuming sorting is not needed, leading to O(n)
• Thinking recursive rebuild is O(n^2) due to repeated subtree calls
• Confusing traversal and construction complexities

4. 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

5. Suppose the BST can contain duplicate values and you want to find the kth smallest element counting duplicates as separate elements. Which modification to the iterative inorder traversal approach correctly handles duplicates without extra space or preprocessing?

hard

A. Perform a full inorder traversal collecting all values, then remove duplicates before indexing kth element.

B. Modify the traversal to skip nodes with duplicate values to avoid counting duplicates multiple times.

C. Use a hash set to track visited values and only increment count for unique values.

D. Keep the traversal unchanged; duplicates are naturally counted separately in inorder traversal order.

Solution

1. Step 1: Understand duplicates in BST inorder traversal

   Inorder traversal visits nodes in sorted order including duplicates as separate nodes.

2. Step 2: Check if modification is needed

   Since duplicates appear as separate nodes, counting each node visited naturally counts duplicates separately without extra logic.

3. Step 3: Evaluate other options

   Skipping duplicates (B) or using a hash set (C) changes semantics. Removing duplicates after full traversal (D) is inefficient and breaks counting duplicates separately.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Inorder traversal inherently counts duplicates separately [OK]

Hint: Duplicates appear as separate nodes in inorder traversal [OK]

Common Mistakes:

• Trying to skip duplicates
• Using extra space unnecessarily
• Assuming duplicates must be merged