LeetCode 173 - Binary Search Tree Iterator

Difficulty: 🟡 Medium
Topics: Stack, Tree, Design, Binary Search Tree, Binary Tree, Iterator

Solution

It looks like your prompt accidentally concatenated two problems. I will answer the second one, LeetCode 173 - Binary Search Tree Iterator, following your required format.

Problem Understanding

This problem asks us to design an iterator for a Binary Search Tree (BST) that returns values in in-order traversal order. In a BST, an in-order traversal visits nodes in ascending sorted order, meaning we visit the left subtree first, then the current node, and finally the right subtree.

The iterator must support three operations:

The constructor initializes the iterator with the BST root.
next() moves to the next smallest number and returns it.
hasNext() checks whether another value exists in the traversal.

The problem guarantees that calls to next() are always valid, meaning we never need to worry about attempting to retrieve a value when none remain.

A key detail is that the iterator pointer starts at a position "before" the smallest element. This means the very first call to next() should return the minimum value in the BST.

The constraints are important here. The tree may contain up to 10^5 nodes, and there may also be up to 10^5 calls to next() and hasNext(). A naive solution that repeatedly traverses the tree for every operation would be inefficient. The follow up specifically asks for an implementation with average O(1) time per operation and O(h) memory, where h is the tree height.

There are several edge cases to consider. A tree with only one node should behave correctly, returning the node once and then reporting no remaining elements. A completely left-skewed tree creates the deepest possible traversal stack, while a right-skewed tree tests whether we correctly move through right children. Large balanced trees also matter because the follow up specifically targets height-based memory efficiency.

Approaches

Brute Force Approach

A straightforward solution is to perform a complete in-order traversal during initialization, store all values in an array, and maintain an index pointer.

This works because an in-order traversal of a BST naturally produces values in sorted ascending order. Once we have the full traversal sequence stored, next() simply increments an index and returns the next element, while hasNext() checks whether the index has reached the end of the array.

Although correct, this approach does not satisfy the follow up requirements. It requires O(n) memory because every node value is stored upfront. Initialization also costs O(n) time because the entire tree must be traversed before iteration even begins.

Optimal Approach

The better solution is to simulate the in-order traversal lazily using a stack.

The key insight is that in-order traversal only needs to remember the path from the root to the current node. Instead of traversing the whole tree in advance, we only preload the leftmost path into a stack. The top of the stack always represents the next smallest node.

When next() is called, we pop the top node because it is the next smallest value. If this node has a right child, we push the entire leftmost path of that right subtree into the stack.

This design achieves the follow up requirement because every node is pushed and popped exactly once. Although a single next() call may occasionally process several nodes, the total work across all operations is linear, giving an average O(1) time complexity. The stack only stores nodes along one root-to-leaf path, so memory usage remains O(h).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Initialization: `O(n)`, `next()`: `O(1)`, `hasNext()`: `O(1)`	`O(n)`	Precompute entire in-order traversal
Optimal	Average `O(1)` per operation	`O(h)`	Lazy in-order traversal using a stack

Algorithm Walkthrough

Initialize an empty stack in the constructor.
Starting from the root, repeatedly move left while pushing every visited node onto the stack. This ensures the smallest element is placed on top of the stack.
When next() is called, pop the top node from the stack. This node is the next smallest value in sorted order.
After popping a node, check whether it has a right child. If it does, move into the right subtree and again push every left descendant onto the stack. This preserves the in-order traversal sequence.
Return the popped node's value.
When hasNext() is called, simply check whether the stack contains any nodes. If it does, another element remains.

Why it works

The algorithm maintains an important invariant: the top of the stack is always the next smallest unvisited node.

Initially, pushing the leftmost path guarantees the smallest node is available first. Whenever a node is removed, its right subtree becomes the next region to explore. By pushing that subtree's leftmost path, we ensure the next smallest node is restored to the top of the stack. Since every node is processed exactly once and in sorted order, the iterator correctly implements in-order traversal.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self._push_left_path(root)

    def _push_left_path(self, node: Optional[TreeNode]) -> None:
        while node:
            self.stack.append(node)
            node = node.left

    def next(self) -> int:
        current_node = self.stack.pop()

        if current_node.right:
            self._push_left_path(current_node.right)

        return current_node.val

    def hasNext(self) -> bool:
        return len(self.stack) > 0

# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

The implementation begins by creating a stack and immediately pushing the leftmost path from the root. This guarantees the smallest value is ready for retrieval.

The helper method _push_left_path() centralizes the logic for walking left and pushing nodes. This avoids duplicating code between the constructor and next().

Inside next(), the top node is popped because it represents the smallest unvisited value. If the popped node has a right subtree, we process its left boundary to preserve in-order ordering.

The hasNext() method remains simple because the stack itself acts as our state tracker. If nodes remain in the stack, another traversal value exists.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type BSTIterator struct {
	stack []*TreeNode
}

func Constructor(root *TreeNode) BSTIterator {
	iterator := BSTIterator{
		stack: []*TreeNode{},
	}

	iterator.pushLeftPath(root)

	return iterator
}

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

func (this *BSTIterator) Next() int {
	lastIndex := len(this.stack) - 1
	currentNode := this.stack[lastIndex]
	this.stack = this.stack[:lastIndex]

	if currentNode.Right != nil {
		this.pushLeftPath(currentNode.Right)
	}

	return currentNode.Val
}

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

/**
 * Your BSTIterator object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */

The Go solution follows the same algorithmic structure as Python. Since Go does not have a built-in stack type, a slice of *TreeNode pointers is used instead. Appending simulates a push operation, while slicing removes the last element for pop behavior.

Unlike Python's dynamic typing, Go explicitly works with pointer types (*TreeNode) to avoid unnecessary copying of tree nodes. No integer overflow concerns exist here because node values remain within the problem constraints.

Worked Examples

Example 1

Input tree:

During initialization, we push the leftmost path:

Step	Current Node	Stack
Start	7	[]
Push 7	3	[7]
Push 3	null	[7, 3]

The stack top is 3, which is the smallest value.

First `next()`

Action	Stack Before	Result
Pop 3	[7, 3]	Return 3

Stack becomes [7].

Second `next()`

Action	Stack Before	Result
Pop 7	[7]	Return 7

Node 7 has right child 15.

Push left path of 15:

Step	Current Node	Stack
Push 15	9	[15]
Push 9	null	[15, 9]

`hasNext()`

Stack is non-empty, return true.

Third `next()`

Pop 9.

Stack becomes [15].

Return 9.

The sequence continues as:

15 → 20

After popping 20, the stack becomes empty, so hasNext() returns false.

Complexity Analysis

Measure	Complexity	Explanation
Time	Average `O(1)`	Each node is pushed and popped exactly once
Space	`O(h)`	Stack stores at most one root-to-leaf path

Although an individual next() call may occasionally take O(h) time when processing a deep right subtree, each node enters and leaves the stack exactly once across the entire execution. Therefore, amortized complexity becomes O(1) per operation.

Test Cases

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

# Example 1
root = TreeNode(
    7,
    TreeNode(3),
    TreeNode(15, TreeNode(9), TreeNode(20))
)

iterator = BSTIterator(root)

assert iterator.next() == 3      # Smallest element
assert iterator.next() == 7      # Second smallest
assert iterator.hasNext() is True  # More nodes remain
assert iterator.next() == 9      # Left child of right subtree
assert iterator.hasNext() is True
assert iterator.next() == 15
assert iterator.hasNext() is True
assert iterator.next() == 20     # Largest element
assert iterator.hasNext() is False  # No more nodes

# Single node tree
root = TreeNode(42)

iterator = BSTIterator(root)

assert iterator.next() == 42     # Only node
assert iterator.hasNext() is False  # Iterator exhausted

# Left-skewed tree
root = TreeNode(3, TreeNode(2, TreeNode(1)))

iterator = BSTIterator(root)

assert iterator.next() == 1      # Smallest node
assert iterator.next() == 2
assert iterator.next() == 3
assert iterator.hasNext() is False

# Right-skewed tree
root = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))

iterator = BSTIterator(root)

assert iterator.next() == 1
assert iterator.next() == 2
assert iterator.next() == 3
assert iterator.hasNext() is False

# Balanced BST
root = TreeNode(
    4,
    TreeNode(2, TreeNode(1), TreeNode(3)),
    TreeNode(6, TreeNode(5), TreeNode(7))
)

iterator = BSTIterator(root)

result = []
while iterator.hasNext():
    result.append(iterator.next())

assert result == [1, 2, 3, 4, 5, 6, 7]  # Sorted traversal

Test	Why
Example tree	Verifies standard behavior
Single node	Tests smallest valid tree
Left-skewed tree	Tests deep left traversal
Right-skewed tree	Tests right subtree handling
Balanced BST	Verifies sorted in-order traversal

Edge Cases

Single Node Tree

A BST with only one node is the smallest valid input. This case can expose bugs where initialization assumes children exist or where hasNext() incorrectly reports additional values. The implementation handles this naturally because the constructor pushes the root into the stack, next() removes it, and hasNext() correctly returns False.

Completely Left-Skewed Tree

A tree where every node only has a left child behaves like a linked list. This creates the maximum possible stack depth during initialization. A naive implementation might repeatedly retraverse nodes inefficiently, but our approach pushes each node exactly once during construction and pops them in ascending order.

Completely Right-Skewed Tree

A tree where every node only has a right child tests whether the iterator correctly transitions into right subtrees. After each next() call, the implementation pushes the leftmost path of the right child. Since no left children exist, each right node is added directly, preserving the correct order.

Large Balanced Tree

A balanced BST with up to 10^5 nodes stresses both performance and memory usage. The implementation satisfies the follow up because the stack size never exceeds the tree height, which is O(log n) for balanced trees, while each operation remains amortized O(1).