173. Binary Search Tree Iterator

At a Glance

Topic: trees
Pattern: Iterative inorder (stack)
Difficulty: Medium
Companies: Amazon, Facebook, Google, Microsoft, Bloomberg
Frequency: High
LeetCode: 173

Design an iterator over a BST starting from the smallest element: constructor stores the root; next() returns the next smallest value in ascending order; hasNext() tells whether more exist. Both amortized O(1) time are expected.

Recognition Cues

Controlled inorder traversal without materializing full list up front
Stack holds the left spine; popping visits node; then push left spine of right child
Same machinery as 230 kth smallest stopped incrementally

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — inorder into array, index pointer — O(n) memory upfront.
Optimal — lazy stack inorder — O(h) stack, amortized O(1) per next() across full traversal.

Optimal Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type BSTIterator struct {
	stack []*TreeNode
}

func Constructor(root *TreeNode) BSTIterator {
	iter := BSTIterator{stack: []*TreeNode{}}
	iter.pushLeftBranch(root)
	return iter
}

func (iter *BSTIterator) pushLeftBranch(node *TreeNode) {
	for node != nil {
		iter.stack = append(iter.stack, node)
		node = node.Left
	}
}

func (iter *BSTIterator) Next() int {
	last := len(iter.stack) - 1
	node := iter.stack[last]
	iter.stack = iter.stack[:last]
	iter.pushLeftBranch(node.Right)
	return node.Val
}

func (iter *BSTIterator) HasNext() bool {
	return len(iter.stack) > 0
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

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

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

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

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