BST Iterator (In-Order Next)

🎯

BST Iterator (In-Order Next)

mediumTREEAmazonFacebookMicrosoft

Imagine you are browsing a sorted collection of items stored in a BST, and you want to efficiently get the next smallest item each time you ask, without traversing the entire tree repeatedly.

💡 This problem is about designing an iterator that returns the next smallest element in a BST on demand. Beginners often struggle because they try to traverse the entire tree upfront or don't understand how to maintain state between calls efficiently.

📋

Problem Statement

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST. Implement the BSTIterator class: BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST. boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false. int next() Moves the pointer to the right, then returns the number at the pointer.

The number of nodes in the tree is in the range [1, 10^5].0 <= Node.val <= 10^6At most 10^5 calls will be made to hasNext and next.next() and hasNext() should run in average O(1) time and use O(h) memory, where h is the height of the tree.

💡

Example

Input"root = [7,3,15,null,null,9,20], calls = [next(), next(), hasNext(), next(), hasNext(), next(), hasNext(), next(), hasNext()]"

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

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.

• Single node tree → next() returns that node, hasNext() false after
• Left skewed tree → iterator returns nodes in ascending order (which is reverse of insertion order)
• Right skewed tree → iterator returns nodes in ascending order (same as insertion order)
• Repeated calls to hasNext() without next() → should not advance iterator

⚠️

Common Mistakes

Storing all nodes in a list but forgetting to reset pointer correctly

next() returns wrong elements or IndexError

✅ Initialize pointer to -1 and increment before accessing list

Not pushing all left descendants initially in stack approach

next() returns incorrect order or crashes

✅ Implement helper to push all left children from current node

In stack approach, forgetting to push left descendants of right child after popping

Iterator skips nodes or returns wrong order

✅ After popping, call pushLeft on popped node's right child

Modifying tree in Morris traversal but not restoring threads

Tree structure corrupted after iteration

✅ Always remove threads after visiting predecessor

Calling next() without checking hasNext()

Runtime error or undefined behavior when no elements remain

✅ Always check hasNext() before next() in client code

🧠

Brute Force (Full Inorder Traversal Preprocessing)

💡 This approach exists to build intuition by doing the simplest thing: traverse the entire BST upfront and store the sorted elements. It helps beginners understand the problem before optimizing.

Intuition

Perform a full inorder traversal of the BST to get a sorted list of all elements. Then, iterate over this list to return the next smallest element on each call.

Algorithm

1. Traverse the BST inorder and store all node values in a list.
2. Maintain an index pointer initialized to -1.
3. For next(), increment the pointer and return the element at that index.
4. For hasNext(), check if the pointer + 1 is within the list bounds.

💡 The main difficulty is realizing that inorder traversal produces sorted order and that storing all elements upfront is simple but costly.

</>

Code

class BSTIterator:
    def __init__(self, root):
        self.nodes_sorted = []
        self.index = -1
        self._inorder(root)

    def _inorder(self, root):
        if root is None:
            return
        self._inorder(root.left)
        self.nodes_sorted.append(root.val)
        self._inorder(root.right)

    def next(self):
        self.index += 1
        return self.nodes_sorted[self.index]

    def hasNext(self):
        return self.index + 1 < len(self.nodes_sorted)

# Driver code example:
# root = TreeNode(7, TreeNode(3), TreeNode(15, TreeNode(9), TreeNode(20)))
# iterator = BSTIterator(root)
# print(iterator.next())  # 3
# print(iterator.next())  # 7
# print(iterator.hasNext())  # True
# print(iterator.next())  # 9
# print(iterator.hasNext())  # True
# print(iterator.next())  # 15
# print(iterator.hasNext())  # True
# print(iterator.next())  # 20
# print(iterator.hasNext())  # False

Line Notes

self.nodes_sorted = []Initialize list to store all BST elements in sorted order

self.index = -1Start pointer before the first element to prepare for next() calls

self._inorder(root)Perform full inorder traversal to fill nodes_sorted

self.nodes_sorted.append(root.val)Add current node's value to the sorted list

self.index += 1Move pointer forward to get next smallest element

return self.nodes_sorted[self.index]Return the element at the current pointer

return self.index + 1 < len(self.nodes_sorted)Check if more elements remain after current pointer

import java.util.*;

class BSTIterator {
    private List<Integer> nodesSorted;
    private int index;

    public BSTIterator(TreeNode root) {
        nodesSorted = new ArrayList<>();
        index = -1;
        inorder(root);
    }

    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        nodesSorted.add(root.val);
        inorder(root.right);
    }

    public int next() {
        index++;
        return nodesSorted.get(index);
    }

    public boolean hasNext() {
        return index + 1 < nodesSorted.size();
    }

    // Driver code example:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(7, new TreeNode(3), new TreeNode(15, new TreeNode(9), new TreeNode(20)));
    //     BSTIterator iterator = new BSTIterator(root);
    //     System.out.println(iterator.next());  // 3
    //     System.out.println(iterator.next());  // 7
    //     System.out.println(iterator.hasNext());  // true
    //     System.out.println(iterator.next());  // 9
    //     System.out.println(iterator.hasNext());  // true
    //     System.out.println(iterator.next());  // 15
    //     System.out.println(iterator.hasNext());  // true
    //     System.out.println(iterator.next());  // 20
    //     System.out.println(iterator.hasNext());  // false
    // }
}

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val; this.left = left; this.right = right;
    }
}

Line Notes

nodesSorted = new ArrayList<>();Initialize list to hold sorted BST elements

index = -1;Pointer starts before first element for next()

inorder(root);Fill nodesSorted with inorder traversal

nodesSorted.add(root.val);Add current node's value to sorted list

index++;Advance pointer to next element

return nodesSorted.get(index);Return element at current pointer

return index + 1 < nodesSorted.size();Check if more elements remain

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class BSTIterator {
    vector<int> nodesSorted;
    int index;

    void inorder(TreeNode* root) {
        if (!root) return;
        inorder(root->left);
        nodesSorted.push_back(root->val);
        inorder(root->right);
    }

public:
    BSTIterator(TreeNode* root) {
        index = -1;
        inorder(root);
    }

    int next() {
        index++;
        return nodesSorted[index];
    }

    bool hasNext() {
        return index + 1 < (int)nodesSorted.size();
    }
};

// Driver code example:
// int main() {
//     TreeNode* root = new TreeNode(7);
//     root->left = new TreeNode(3);
//     root->right = new TreeNode(15);
//     root->right->left = new TreeNode(9);
//     root->right->right = new TreeNode(20);
//     BSTIterator iterator(root);
//     cout << iterator.next() << endl;  // 3
//     cout << iterator.next() << endl;  // 7
//     cout << iterator.hasNext() << endl;  // 1 (true)
//     cout << iterator.next() << endl;  // 9
//     cout << iterator.hasNext() << endl;  // 1 (true)
//     cout << iterator.next() << endl;  // 15
//     cout << iterator.hasNext() << endl;  // 1 (true)
//     cout << iterator.next() << endl;  // 20
//     cout << iterator.hasNext() << endl;  // 0 (false)
//     return 0;
// }

Line Notes

vector<int> nodesSorted;Stores all BST elements in sorted order

int index;Pointer to track current position in nodesSorted

inorder(root);Populate nodesSorted with inorder traversal

nodesSorted.push_back(root->val);Add current node's value to vector

index++;Move pointer forward for next element

return nodesSorted[index];Return element at current pointer

return index + 1 < (int)nodesSorted.size();Check if more elements remain

class BSTIterator {
    constructor(root) {
        this.nodesSorted = [];
        this.index = -1;
        this._inorder(root);
    }

    _inorder(root) {
        if (!root) return;
        this._inorder(root.left);
        this.nodesSorted.push(root.val);
        this._inorder(root.right);
    }

    next() {
        this.index++;
        return this.nodesSorted[this.index];
    }

    hasNext() {
        return this.index + 1 < this.nodesSorted.length;
    }
}

// Driver code example:
// const root = { val: 7, left: { val: 3, left: null, right: null }, right: { val: 15, left: { val: 9, left: null, right: null }, right: { val: 20, left: null, right: null } } };
// const iterator = new BSTIterator(root);
// console.log(iterator.next());  // 3
// console.log(iterator.next());  // 7
// console.log(iterator.hasNext());  // true
// console.log(iterator.next());  // 9
// console.log(iterator.hasNext());  // true
// console.log(iterator.next());  // 15
// console.log(iterator.hasNext());  // true
// console.log(iterator.next());  // 20
// console.log(iterator.hasNext());  // false

Line Notes

this.nodesSorted = []Initialize array to hold sorted BST elements

this.index = -1Pointer starts before first element for next()

this._inorder(root)Fill nodesSorted with inorder traversal

this.nodesSorted.push(root.val)Add current node's value to array

this.index++Advance pointer to next element

return this.nodesSorted[this.index]Return element at current pointer

return this.index + 1 < this.nodesSorted.lengthCheck if more elements remain

⏱

Complexity

TimeO(n) preprocessing, O(1) per next()/hasNext() call

SpaceO(n) to store all nodes in a list

We traverse all nodes once to build the list, then each next/hasNext is just pointer arithmetic.

💡 For n=100,000 nodes, this means 100,000 operations upfront, then constant time per call.

Interview Verdict: Accepted but inefficient for large trees due to O(n) space

This approach is easy to implement but uses too much memory and is not optimal for large inputs.

🧠

Controlled Inorder Traversal Using Stack (Lazy Evaluation)

💡 This approach improves space by not storing all nodes upfront. Instead, it simulates inorder traversal using a stack, pushing nodes only as needed.

Intuition

Use a stack to simulate the recursion of inorder traversal. Push all left children initially, then on next(), pop from stack and push the right child's left descendants.

Algorithm

1. Initialize a stack and push all left children of root onto it.
2. For next(), pop the top node from the stack (this is the next smallest).
3. If the popped node has a right child, push all its left descendants onto the stack.
4. hasNext() returns true if the stack is not empty.

💡 The challenge is managing the stack correctly to maintain the inorder traversal state without recursion.

</>

Code

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self):
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val

    def hasNext(self):
        return len(self.stack) > 0

# Driver code example:
# root = TreeNode(7, TreeNode(3), TreeNode(15, TreeNode(9), TreeNode(20)))
# iterator = BSTIterator(root)
# print(iterator.next())  # 3
# print(iterator.next())  # 7
# print(iterator.hasNext())  # True
# print(iterator.next())  # 9
# print(iterator.hasNext())  # True
# print(iterator.next())  # 15
# print(iterator.hasNext())  # True
# print(iterator.next())  # 20
# print(iterator.hasNext())  # False

Line Notes

self.stack = []Stack holds nodes to visit next in inorder

self._push_left(root)Push all left descendants of root to stack initially

while node:Traverse down left children pushing onto stack

node = node.leftMove left to reach smallest nodes first

node = self.stack.pop()Pop next smallest node from stack

self._push_left(node.right)Push left descendants of right child to stack

return len(self.stack) > 0Check if more nodes remain to visit

import java.util.*;

class BSTIterator {
    private Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        pushLeft(root);
    }

    private void pushLeft(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }

    public int next() {
        TreeNode node = stack.pop();
        pushLeft(node.right);
        return node.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

    // Driver code example:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(7, new TreeNode(3), new TreeNode(15, new TreeNode(9), new TreeNode(20)));
    //     BSTIterator iterator = new BSTIterator(root);
    //     System.out.println(iterator.next());  // 3
    //     System.out.println(iterator.next());  // 7
    //     System.out.println(iterator.hasNext());  // true
    //     System.out.println(iterator.next());  // 9
    //     System.out.println(iterator.hasNext());  // true
    //     System.out.println(iterator.next());  // 15
    //     System.out.println(iterator.hasNext());  // true
    //     System.out.println(iterator.next());  // 20
    //     System.out.println(iterator.hasNext());  // false
    // }
}

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val; this.left = left; this.right = right;
    }
}

Line Notes

stack = new Stack<>();Stack stores nodes to visit in inorder

pushLeft(root);Push all left descendants of root initially

while (node != null)Traverse left children pushing onto stack

stack.push(node);Remember nodes to visit later

TreeNode node = stack.pop();Pop next smallest node

pushLeft(node.right);Push left descendants of right child

return !stack.isEmpty();Check if more nodes remain

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class BSTIterator {
    stack<TreeNode*> st;

    void pushLeft(TreeNode* node) {
        while (node) {
            st.push(node);
            node = node->left;
        }
    }

public:
    BSTIterator(TreeNode* root) {
        pushLeft(root);
    }

    int next() {
        TreeNode* node = st.top();
        st.pop();
        pushLeft(node->right);
        return node->val;
    }

    bool hasNext() {
        return !st.empty();
    }
};

// Driver code example:
// int main() {
//     TreeNode* root = new TreeNode(7);
//     root->left = new TreeNode(3);
//     root->right = new TreeNode(15);
//     root->right->left = new TreeNode(9);
//     root->right->right = new TreeNode(20);
//     BSTIterator iterator(root);
//     cout << iterator.next() << endl;  // 3
//     cout << iterator.next() << endl;  // 7
//     cout << iterator.hasNext() << endl;  // 1 (true)
//     cout << iterator.next() << endl;  // 9
//     cout << iterator.hasNext() << endl;  // 1 (true)
//     cout << iterator.next() << endl;  // 15
//     cout << iterator.hasNext() << endl;  // 1 (true)
//     cout << iterator.next() << endl;  // 20
//     cout << iterator.hasNext() << endl;  // 0 (false)
//     return 0;
// }

Line Notes

stack<TreeNode*> st;Stack holds nodes to visit in inorder

void pushLeft(TreeNode* node)Push all left descendants of node onto stack

while (node)Traverse down left children

st.push(node);Remember nodes for later visitation

TreeNode* node = st.top();Get next smallest node

st.pop();Remove node from stack after visiting

pushLeft(node->right);Push left descendants of right child

class BSTIterator {
    constructor(root) {
        this.stack = [];
        this._pushLeft(root);
    }

    _pushLeft(node) {
        while (node !== null) {
            this.stack.push(node);
            node = node.left;
        }
    }

    next() {
        const node = this.stack.pop();
        this._pushLeft(node.right);
        return node.val;
    }

    hasNext() {
        return this.stack.length > 0;
    }
}

// Driver code example:
// const root = { val: 7, left: { val: 3, left: null, right: null }, right: { val: 15, left: { val: 9, left: null, right: null }, right: { val: 20, left: null, right: null } } };
// const iterator = new BSTIterator(root);
// console.log(iterator.next());  // 3
// console.log(iterator.next());  // 7
// console.log(iterator.hasNext());  // true
// console.log(iterator.next());  // 9
// console.log(iterator.hasNext());  // true
// console.log(iterator.next());  // 15
// console.log(iterator.hasNext());  // true
// console.log(iterator.next());  // 20
// console.log(iterator.hasNext());  // false

Line Notes

this.stack = []Stack stores nodes to visit in inorder

this._pushLeft(root)Push all left descendants of root initially

while (node !== null)Traverse left children pushing onto stack

this.stack.push(node)Remember nodes for later visitation

const node = this.stack.pop()Pop next smallest node

this._pushLeft(node.right)Push left descendants of right child

return this.stack.length > 0Check if more nodes remain

⏱

Complexity

TimeAverage O(1) per next()/hasNext() call, O(h) worst case for next()

SpaceO(h) where h is tree height due to stack

Each node is pushed and popped once, so total O(n) over n calls; amortized O(1) per call.

💡 For a balanced tree with height ~log n, stack size is small, making this efficient for large trees.

Interview Verdict: Accepted and optimal for interview coding

This approach balances time and space well and is the standard solution expected in interviews.

🧠

Morris Inorder Traversal (Threaded Binary Tree) for O(1) Space

💡 This advanced approach uses threaded binary trees to achieve O(1) space without a stack or recursion. It is less common but shows deep understanding of tree traversal.

Intuition

Modify the tree temporarily by creating threads to predecessor nodes, allowing inorder traversal without extra space. Restore the tree after traversal.

Algorithm

1. Initialize current node as root.
2. While current is not null, if current has no left child, visit it and move to right child.
3. If current has left child, find its inorder predecessor (rightmost node in left subtree).
4. If predecessor's right is null, set it to current (thread), move current to left child.
5. If predecessor's right is current, revert the thread to null, visit current, move to right child.

💡 The tricky part is creating and removing threads to simulate recursion without extra memory.

</>

Code

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:
                    pre.right = None
                    self.next_val = self.current.val
                    self.current = self.current.right
                    return
        self.next_val = None

    def next(self):
        val = self.next_val
        self._advance()
        return val

    def hasNext(self):
        return self.next_val is not None

# Driver code example:
# root = TreeNode(7, TreeNode(3), TreeNode(15, TreeNode(9), TreeNode(20)))
# iterator = BSTIterator(root)
# print(iterator.next())  # 3
# print(iterator.next())  # 7
# print(iterator.hasNext())  # True
# print(iterator.next())  # 9
# print(iterator.hasNext())  # True
# print(iterator.next())  # 15
# print(iterator.hasNext())  # True
# print(iterator.next())  # 20
# print(iterator.hasNext())  # False

Line Notes

self.current = rootStart traversal from root node

self._advance()Precompute the next value to return

if not self.current.leftIf no left child, current node is next in inorder

pre = self.current.leftFind inorder predecessor in left subtree

pre.right = self.currentCreate thread to current node

pre.right = NoneRemove thread after visiting left subtree

self.next_val = NoneMark end of traversal when no nodes left

class BSTIterator {
    private TreeNode current;
    private Integer nextVal;

    public BSTIterator(TreeNode root) {
        current = root;
        advance();
    }

    private void advance() {
        while (current != null) {
            if (current.left == null) {
                nextVal = current.val;
                current = current.right;
                return;
            } else {
                TreeNode pre = current.left;
                while (pre.right != null && pre.right != current) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    pre.right = current;
                    current = current.left;
                } else {
                    pre.right = null;
                    nextVal = current.val;
                    current = current.right;
                    return;
                }
            }
        }
        nextVal = null;
    }

    public int next() {
        int val = nextVal;
        advance();
        return val;
    }

    public boolean hasNext() {
        return nextVal != null;
    }

    // Driver code example:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(7, new TreeNode(3), new TreeNode(15, new TreeNode(9), new TreeNode(20)));
    //     BSTIterator iterator = new BSTIterator(root);
    //     System.out.println(iterator.next());  // 3
    //     System.out.println(iterator.next());  // 7
    //     System.out.println(iterator.hasNext());  // true
    //     System.out.println(iterator.next());  // 9
    //     System.out.println(iterator.hasNext());  // true
    //     System.out.println(iterator.next());  // 15
    //     System.out.println(iterator.hasNext());  // true
    //     System.out.println(iterator.next());  // 20
    //     System.out.println(iterator.hasNext());  // false
    // }
}

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val; this.left = left; this.right = right;
    }
}

Line Notes

current = root;Initialize traversal at root

advance();Precompute next value to return

if (current.left == null)If no left child, current node is next inorder

TreeNode pre = current.left;Find inorder predecessor

pre.right = current;Create thread to current node

pre.right = null;Remove thread after visiting left subtree

nextVal = null;Mark traversal end

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class BSTIterator {
    TreeNode* current;
    int nextVal;
    bool has_next;

    void advance() {
        while (current) {
            if (!current->left) {
                nextVal = current->val;
                current = current->right;
                has_next = true;
                return;
            } else {
                TreeNode* pre = current->left;
                while (pre->right && pre->right != current) {
                    pre = pre->right;
                }
                if (!pre->right) {
                    pre->right = current;
                    current = current->left;
                } else {
                    pre->right = nullptr;
                    nextVal = current->val;
                    current = current->right;
                    has_next = true;
                    return;
                }
            }
        }
        has_next = false;
    }

public:
    BSTIterator(TreeNode* root) {
        current = root;
        has_next = false;
        advance();
    }

    int next() {
        int val = nextVal;
        advance();
        return val;
    }

    bool hasNext() {
        return has_next;
    }
};

// Driver code example:
// int main() {
//     TreeNode* root = new TreeNode(7);
//     root->left = new TreeNode(3);
//     root->right = new TreeNode(15);
//     root->right->left = new TreeNode(9);
//     root->right->right = new TreeNode(20);
//     BSTIterator iterator(root);
//     cout << iterator.next() << endl;  // 3
//     cout << iterator.next() << endl;  // 7
//     cout << iterator.hasNext() << endl;  // 1 (true)
//     cout << iterator.next() << endl;  // 9
//     cout << iterator.hasNext() << endl;  // 1 (true)
//     cout << iterator.next() << endl;  // 15
//     cout << iterator.hasNext() << endl;  // 1 (true)
//     cout << iterator.next() << endl;  // 20
//     cout << iterator.hasNext() << endl;  // 0 (false)
//     return 0;
// }

Line Notes

TreeNode* current;Pointer to current node in traversal

void advance()Move to next inorder node using threading

if (!current->left)If no left child, current node is next

TreeNode* pre = current->left;Find inorder predecessor

pre->right = current;Create thread to current node

pre->right = nullptr;Remove thread after visiting left subtree

has_next = false;Mark traversal end

class BSTIterator {
    constructor(root) {
        this.current = root;
        this.nextVal = null;
        this.hasNextVal = false;
        this._advance();
    }

    _advance() {
        while (this.current !== null) {
            if (this.current.left === null) {
                this.nextVal = this.current.val;
                this.current = this.current.right;
                this.hasNextVal = true;
                return;
            } else {
                let pre = this.current.left;
                while (pre.right !== null && pre.right !== this.current) {
                    pre = pre.right;
                }
                if (pre.right === null) {
                    pre.right = this.current;
                    this.current = this.current.left;
                } else {
                    pre.right = null;
                    this.nextVal = this.current.val;
                    this.current = this.current.right;
                    this.hasNextVal = true;
                    return;
                }
            }
        }
        this.hasNextVal = false;
    }

    next() {
        const val = this.nextVal;
        this._advance();
        return val;
    }

    hasNext() {
        return this.hasNextVal;
    }
}

// Driver code example:
// const root = { val: 7, left: { val: 3, left: null, right: null }, right: { val: 15, left: { val: 9, left: null, right: null }, right: { val: 20, left: null, right: null } } };
// const iterator = new BSTIterator(root);
// console.log(iterator.next());  // 3
// console.log(iterator.next());  // 7
// console.log(iterator.hasNext());  // true
// console.log(iterator.next());  // 9
// console.log(iterator.hasNext());  // true
// console.log(iterator.next());  // 15
// console.log(iterator.hasNext());  // true
// console.log(iterator.next());  // 20
// console.log(iterator.hasNext());  // false

Line Notes

this.current = rootStart traversal at root node

this._advance()Precompute next value to return

if (this.current.left === null)If no left child, current node is next inorder

let pre = this.current.leftFind inorder predecessor

pre.right = this.currentCreate thread to current node

pre.right = nullRemove thread after visiting left subtree

this.hasNextVal = falseMark traversal end

⏱

Complexity

TimeO(n) total, O(1) average per next()/hasNext() call

SpaceO(1) extra space, modifies tree temporarily

Each edge is visited at most twice, no stack needed, so total O(n) time and constant space.

💡 This is the most space-efficient method but is complex and modifies the tree temporarily, which may not be allowed.

Interview Verdict: Accepted but rarely used in interviews due to complexity

Good to mention for deep knowledge, but usually not expected to implement fully in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 The stack-based controlled inorder traversal is the best balance of simplicity and efficiency, and is what you should code in 95% of interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n) preprocessing, O(1) per call	O(n)	No	Yes	Mention only - never code
2. Controlled Inorder Traversal Using Stack	O(1) average per call	O(h)	No	Yes	Code this approach
3. Morris Inorder Traversal	O(1) average per call	O(1)	No	No (modifies tree temporarily)	Mention only if asked about space optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, start with brute force to build intuition, then move to stack-based controlled traversal for optimal solution. Practice coding and explaining each step clearly.

How to Present

Step 1: Clarify problem requirements and constraints.Step 2: Describe brute force approach with full inorder traversal and list storage.Step 3: Explain inefficiency and introduce stack-based controlled inorder traversal.Step 4: Code the stack-based approach carefully, explaining stack usage.Step 5: Discuss time and space complexity and possible follow-ups.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test & Discuss: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests understanding of inorder traversal, ability to maintain state between calls, and optimization from naive to efficient iterator.

Common Follow-ups

• Can you reduce space usage further? → Mention Morris traversal.
• What if the BST is modified during iteration? → Discuss invalidation and reinitialization.

💡 Follow-ups test deeper understanding of traversal techniques and iterator robustness.

🔍

Pattern Recognition

When to Use

1) Need to iterate BST in sorted order 2) Must support next() and hasNext() calls 3) Want efficient average O(1) time per call 4) Space usage should be better than O(n)

Signature Phrases

'next smallest number in the BST''pointer initialized to a number smaller than any element''hasNext() returns true if there exists a next number'

NOT This Pattern When

Problems that require full tree modification or random access rather than sequential iteration

Similar Problems

Binary Tree Inorder Traversal - basic inorder traversalKth Smallest Element in a BST - uses similar controlled traversalFlatten Binary Tree to Linked List - related tree traversal and manipulation

Practice

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

2. Examine the following code snippet intended to balance a BST by collecting nodes via inorder traversal and rebuilding the tree. Identify the subtle bug that could cause incorrect tree structure or cycles.

medium

A. The left and right pointers of nodes are not reset before rebuilding.

B. The inorder traversal appends nodes instead of values.

C. The middle index calculation uses integer division which may skew balance.

D. The stack is popped instead of dequeued, reversing processing order.

Solution

1. Step 1: Identify pointer reset necessity

   When rebuilding, left and right pointers must be reset to avoid old links causing cycles.

2. Step 2: Locate missing reset in code

   Commented out line resetting node.left and node.right causes bug.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Not resetting pointers -> cycles or incorrect tree [OK]

Hint: Always reset node pointers when rebuilding trees [OK]

Common Mistakes:

• Ignoring pointer reset leads to subtle bugs
• Misunderstanding traversal appending nodes is correct
• Thinking stack order affects correctness here

3. What is the time complexity of the optimal iterative approach that converts a BST to a Greater Tree using reverse inorder traversal with an explicit stack?

medium

A. O(n) where n is the number of nodes in the BST

B. O(n · h) where n is number of nodes and h is tree height

C. O(n · log n) due to stack operations on balanced BST

D. O(h) where h is the height of the BST because each node is visited once

Solution

1. Step 1: Identify number of nodes visited

   Each node is visited exactly once during traversal.

2. Step 2: Analyze stack operations and overall traversal

   While each node is visited once, the explicit stack can hold up to h nodes, and each push/pop operation can be considered O(1). However, in the worst case (unbalanced tree), the height h can be up to n, making the complexity O(n * h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Worst-case complexity depends on tree height [OK]

Hint: Worst-case complexity depends on tree height [OK]

Common Mistakes:

• Assuming stack operations multiply complexity by height unnecessarily
• Confusing recursion stack space with time complexity
• Thinking balanced BST implies O(n log n) time

4. Suppose the BST deletion operation is modified so that duplicate keys are allowed and stored in the right subtree. How should the deletion algorithm be adapted to correctly delete a node with duplicates?

hard

A. Always delete the first occurrence found and ignore duplicates in the right subtree.

B. Replace the node with its in-order predecessor instead of successor to handle duplicates correctly.

C. Modify the successor search to find the leftmost node with the same key in the right subtree before deletion.

D. When deleting a node with duplicates, delete the node and recursively delete all duplicates in the right subtree with the same key.

Solution

1. Step 1: Understand duplicates stored in right subtree

   Duplicates appear as nodes with the same key in the right subtree, so deleting one occurrence requires deleting all duplicates to maintain correctness.

2. Step 2: Adapt deletion to remove all duplicates

   After deleting the target node, recursively delete all nodes in the right subtree with the same key to remove duplicates fully.

3. Step 3: Why other options fail

   Ignoring duplicates leaves them in tree (A), replacing with predecessor doesn't address duplicates (B), and modifying successor search (D) doesn't remove all duplicates.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Deleting all duplicates ensures BST correctness with duplicates allowed [OK]

Hint: Duplicates require recursive deletion of all matching keys [OK]

Common Mistakes:

• Deleting only one node leaves duplicates
• Using predecessor doesn't solve duplicates
• Modifying successor search misses duplicates

5. Suppose the BST can contain duplicate values and you want to find if there exist two nodes (not necessarily distinct) whose values sum to k. Which modification to the optimal inorder + two-pointer approach correctly handles this scenario?

hard

A. Perform inorder traversal and remove duplicates before applying two-pointer technique.

B. Use the same two-pointer approach but allow left and right pointers to point to the same index.

C. Use a hash set to store values and check complements, ignoring duplicates.

D. During two-pointer traversal, if left == right, check if the value at that index appears at least twice in the BST.

Solution

1. Step 1: Understand duplicates and two-pointer constraints

   Two-pointer approach requires two distinct indices; if pointers meet, need to verify if duplicate values exist.

2. Step 2: Modify check when left == right

   Check if the value at that index occurs at least twice in the BST to allow sum with itself.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only During two-pointer traversal, if left == right, check if the value at that index appears at least twice in the BST. correctly handles duplicates without breaking two-pointer logic [OK]

Hint: Check duplicates count when pointers meet [OK]

Common Mistakes:

• Allowing pointers to be equal without duplicate check
• Removing duplicates loses valid pairs
• Ignoring duplicates in hash set approach