173. Binary Search Tree Iterator

Quick Identifier

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

Quick Sights

Time Complexity: O(h) from the optimal approach.
Space Complexity: O(1) from the optimal approach.
Core Mechanism: 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.

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.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

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

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

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;
	}
}