Binary Search Tree Iterator Visualizer & Step-by-Step Algorithm Solution

Implement an in-order traversal iterator over a Binary Search Tree (BST) using an explicit LIFO stack to achieve O(h) memory and O(1) amortized time.

Category: trees | Difficulty: Medium

Tags: BST, Binary Search Tree, Stack, Design, Inorder Traversal, Tree

Binary Search Tree Iterator

7
7
3
15
9
20
In-Order Output
Push / Pop (Top)
(Empty Stack)
Iterator Stack (LIFO)
100%
state
stack[]
length0
count0
nodeempty
root7
Constructor
1/49
Explanation

Initialize BSTIterator with root: Node(7). Stack initialized to [].

Source Code
1class BSTIterator {
2 private stack: TreeNode[] = [];
3 constructor(root: TreeNode | null) {
4 this.pushLeft(root);
5 }
6 next(): number {
7 const node = this.stack.pop()!;
8 this.pushLeft(node.right);
9 return node.val;
10 }
11 hasNext(): boolean {
12 return this.stack.length > 0;
13 }
14 private pushLeft(node: TreeNode | null): void {
15 while (node) {
16 this.stack.push(node);
17 node = node.left;
18 }
19 }
20}
03 — Reference
ACTIVE