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. You are given a binary search tree and asked to find the kth smallest element efficiently without traversing the entire tree. Which approach best guarantees an optimal solution in terms of time and space complexity?

easy

A. Perform a full inorder traversal to collect all elements in a list, then return the kth element from the list.

B. Use an iterative inorder traversal with a stack, stopping as soon as the kth smallest element is found.

C. Apply a greedy approach by always moving to the left child until k steps are taken.

D. Use dynamic programming to store counts of nodes in subtrees and then navigate to the kth element.

Solution

1. Step 1: Understand the problem constraints

   We want to find the kth smallest element in a BST efficiently, avoiding unnecessary traversal.

2. Step 2: Evaluate approaches

   Full inorder traversal (A) is correct but not optimal since it traverses the entire tree. Greedy left moves (C) fail because the kth element may not be in the leftmost path. DP (D) is complex and not standard for this problem. Iterative inorder with early stopping (B) visits only needed nodes, achieving O(H + k) time and O(H) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Iterative inorder with early stopping avoids full traversal [OK]

Hint: Early stopping in inorder traversal is optimal [OK]

Common Mistakes:

• Assuming full traversal is necessary
• Confusing greedy left moves with inorder traversal

2. Given the following code for finding the kth smallest element in a BST, what is the returned value when called with k=2 on the provided tree?

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    current = root
    count = 0

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right

# Tree:
#     3
#    / \
#   1   4
#    \
#     2

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kthSmallest(root, 2))

easy

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Trace the inorder traversal steps

   Stack initially empty, current=root(3). Push 3, move left to 1. Push 1, move left to None. Pop 1 (count=1), move right to 2.

2. Step 2: Continue traversal to find kth=2

   Push 2, move left None. Pop 2 (count=2), return 2 as kth smallest.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Second smallest in BST is 2 [OK]

Hint: Inorder traversal visits nodes in ascending order [OK]

Common Mistakes:

• Off-by-one counting of k
• Returning before incrementing count

3. The following code attempts to convert a BST to a Greater Tree using reverse inorder traversal. Identify the line that contains a subtle bug causing incorrect node values.

medium

A. Line 8: node = node.left instead of node = node.right

B. Line 6: while node: loop condition

C. Line 10: acc_sum += node.val accumulation

D. Line 12: node = node.right traversal after updating node

Solution

1. Step 1: Understand traversal order needed

   Reverse inorder traversal requires visiting right subtree first to accumulate greater values.

2. Step 2: Identify incorrect subtree traversal

   Line 8 incorrectly moves to left child first, reversing traversal order and causing wrong sums.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing node = node.left to node = node.right fixes traversal order [OK]

Hint: Reverse inorder must traverse right subtree first [OK]

Common Mistakes:

• Swapping left and right subtree traversal order
• Resetting acc_sum inside loops
• Updating node values before traversing right subtree

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. Suppose the BST can contain duplicate values and the range is inclusive [low, high]. How should the trimming algorithm be modified to correctly handle duplicates without breaking BST properties?

hard

A. Change all comparisons to strict inequalities (e.g., < low to <= low) to exclude duplicates outside range.

B. Rebuild the BST from scratch after filtering duplicates to ensure correct ordering.

C. Adjust pruning conditions to include nodes equal to low or high by using <= and >= comparisons appropriately.

D. Ignore duplicates during pruning since BST properties guarantee uniqueness.

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can be on left or right subtree depending on implementation; inclusive range means nodes equal to low or high must be kept.

2. Step 2: Modify pruning conditions

   Use <= and >= in comparisons to keep nodes equal to boundaries, ensuring duplicates within range remain.

3. Step 3: Avoid rebuilding

   Rebuilding wastes time and space; pruning with adjusted conditions preserves BST and duplicates correctly.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Inclusive pruning keeps duplicates at boundaries [OK]

Hint: Use inclusive comparisons to keep duplicates within range [OK]

Common Mistakes:

• Using strict inequalities excludes boundary duplicates
• Rebuilding unnecessarily wastes resources