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 the optimal iterative algorithm for finding the lowest common ancestor in a BST, where h is the height of the tree and n is the number of nodes?

medium

A. O(log n), assuming the BST is balanced and height h = log n

B. O(n), because in the worst case the algorithm may visit all nodes

C. O(h), since the algorithm traverses from root down to the split point along one path

D. O(1), because the algorithm uses constant space and simple comparisons

Solution

1. Step 1: Identify traversal path length

   The algorithm moves from root down one path until the split point, visiting at most h nodes.

2. Step 2: Understand h vs n

   Height h can be up to n in worst case (skewed tree), but the question asks for optimal algorithm time complexity, which assumes balanced BST where h = log n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Traversal limited to one root-to-node path in balanced BST [OK]

Hint: Time depends on tree height, not total nodes [OK]

Common Mistakes:

• Confusing worst-case O(n) with average-case O(log n)
• Assuming constant time due to simple comparisons
• Ignoring that recursion stack space is not used here

4. The following code attempts to recover a BST with two swapped nodes using Morris traversal. Identify the line containing the subtle bug that causes incorrect recovery when the swapped nodes are adjacent in inorder traversal.

def recoverTree(root):
    first = second = prev = None
    current = root
    while current:
        if not current.left:
            if prev and prev.val > current.val:
                if not first:
                    first = prev
                    second = current
                else:
                    second = current
            prev = current
            current = current.right
        else:
            pred = current.left
            while pred.right and pred.right != current:
                pred = pred.right
            if not pred.right:
                pred.right = current
                current = current.left
            else:
                pred.right = None
                if prev and prev.val > current.val:
                    if not first:
                        first = prev
                        second = current
                    else:
                        second = current
                prev = current
                current = current.right
    first.val, second.val = second.val, first.val

medium

A. Swapping values at the end without checking if both nodes are found

B. Line setting second = current inside the first if condition

C. Line setting first = prev inside the second if condition

D. Line setting first = prev inside the first if condition

Solution

1. Step 1: Analyze detection of swapped nodes

   The code sets first and second whenever a violation is found, but overwrites them without preserving the first violation's first node.

2. Step 2: Identify the bug in swapping

   The swap at the end assumes both first and second are found, but if only one violation is detected (adjacent nodes swapped), second may be incorrect or null, causing wrong swap.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Swapping without confirming both nodes leads to incorrect recovery in adjacent swaps [OK]

Hint: Must confirm both nodes before swapping values [OK]

Common Mistakes:

• Overwriting first and second on multiple violations
• Swapping values prematurely after first violation
• Not restoring tree structure after Morris traversal

5. Suppose you want to balance a BST but now the tree nodes can have duplicate values and the BST property is relaxed to allow duplicates on either side. Which modification to the balancing algorithm ensures the resulting tree remains valid and balanced?

hard

A. Use preorder traversal instead of inorder to collect nodes, then rebuild.

B. Modify the middle index calculation to always pick the left middle to keep duplicates on left.

C. During inorder traversal, collect nodes preserving duplicates order, then choose middle node as root as usual.

D. Sort the collected nodes by value before rebuilding to handle duplicates properly.

Solution

1. Step 1: Understand duplicates in BST with relaxed property

   Inorder traversal still produces nodes in non-decreasing order preserving duplicates order.

2. Step 2: Rebuild balanced BST using middle node selection

   Choosing middle node as root maintains balance and respects duplicates order.

3. Step 3: Avoid sorting or preorder traversal

   Sorting is unnecessary and preorder breaks sorted order; left middle bias skews balance.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Inorder traversal + middle node rebuild works with duplicates [OK]

Hint: Inorder traversal preserves duplicates order for balanced rebuild [OK]

Common Mistakes:

• Using preorder traversal losing sorted order
• Sorting nodes again causing unnecessary overhead
• Biasing middle index causing unbalanced tree