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 code snippet implementing the optimal iterative approach to convert a BST to a Greater Tree. Given the BST with nodes [2, 1, 3], what is the value of the root node after the function completes?

easy

A. 5

B. 6

C. 3

D. 4

Solution

1. Step 1: Trace reverse inorder traversal order

   Nodes visited in order: 3, 2, 1.

2. Step 2: Accumulate sums and update nodes

   acc_sum=0 initially. - Visit 3: acc_sum=3, node.val=3 - Visit 2: acc_sum=3+2=5, node.val=5 - Visit 1: acc_sum=5+1=6, node.val=6 Root node was 2, updated to 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Root node value after update is 5 [OK]

Hint: Reverse inorder sums nodes from largest to smallest [OK]

Common Mistakes:

• Confusing traversal order and updating nodes too early
• Off-by-one errors in accumulating sums
• Misidentifying which node is root after updates

2. What is the time complexity of the optimal divide-and-conquer approach to convert a sorted array of length n into a height-balanced BST, and why?

medium

A. O(n log n), because each recursive call processes half the array and builds subtrees.

B. O(n), because each element is visited exactly once to create nodes without extra overhead.

C. O(n^2), because the recursion tree has n levels and each level processes n elements.

D. O(log n), because the tree height is log n and only root nodes are created at each level.

Solution

1. Step 1: Analyze recursion calls

   The algorithm visits each element exactly once to create a TreeNode, splitting the array into halves recursively.

2. Step 2: Calculate total work

   Each element is processed once, so total time is proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass over array with divide-and-conquer -> O(n) time [OK]

Hint: Each element processed once -> O(n) time [OK]

Common Mistakes:

• Confusing recursion depth with total work
• Assuming O(n log n) due to recursion

3. Consider the following buggy code snippet for converting a sorted array to a height-balanced BST. Which line contains the subtle bug that can cause infinite recursion or stack overflow?

medium

A. Line 5: left_child = self.helper(nums, left, mid - 1)

B. Line 3: mid = (left + right) // 2

C. Line 7: root.right = self.helper(nums, mid + 1, right)

D. Line 2: if left >= right: return None

Solution

1. Step 1: Understand base case condition

   The base case should be when left > right, not left >= right, to allow single-element subarrays.

2. Step 2: Consequence of incorrect base case

   Using left >= right causes the recursion to skip processing subarrays of size 1, leading to infinite recursion or missing nodes.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Base case must allow left == right to process single elements [OK]

Hint: Base case must be left > right, not left >= right [OK]

Common Mistakes:

• Incorrect base case causing infinite recursion
• Misplaced mid calculation

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

5. The following code attempts to compute the range sum of a BST using iterative DFS with pruning. Identify the line containing the subtle bug that causes incorrect results or inefficiency.

medium

A. Line that appends node.left when node.val < low

B. Line that pops node from stack

C. Line that adds node.val to total

D. Line that appends node.right when node.val is in range

Solution

1. Step 1: Understand pruning logic

   If node.val < low, left subtree nodes are smaller and cannot be in range, so left subtree should be skipped.

2. Step 2: Identify incorrect line

   Appending node.left when node.val < low causes unnecessary traversal of left subtree, violating pruning. It should append node.right instead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct pruning requires appending node.right only when node.val < low [OK]

Hint: Prune left subtree if node.val < low [OK]

Common Mistakes:

• Appending wrong subtree when pruning
• Forgetting to check null nodes