Skip to main content
Talentd

Binary Search Tree Iterator - Solution & Explanation

MediumStackTreeDesignBinary Search Tree21 min readAsked at: Amazon, Microsoft, Apple +5
Practice this problem

Problem Statement

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

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

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

 

Example 1:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

 

Constraints:

  • The number of nodes in the tree is in the range [1, 105].
  • 0 <= Node.val <= 106
  • At most 105 calls will be made to hasNext, and next.

 

Follow up:

  • Could you implement next() and hasNext() to run in average O(1) time and use O(h) memory, where h is the height of the tree?

Approach Overview

Problem Overview: Design an iterator over a Binary Search Tree (BST) that returns nodes in ascending order. The iterator must support next() and hasNext() while maintaining the BST’s in-order traversal sequence.

Approach 1: Using Stack for Controlled In-order Traversal (Time: O(n) total, O(1) amortized per operation, Space: O(h))

This approach simulates the recursive in-order traversal of a binary tree using an explicit stack. The key idea is to preload the stack with the entire left spine of the tree during initialization. The top of the stack always represents the next smallest node. When next() is called, you pop the top node and then push the left spine of its right child. This ensures the stack always holds the next valid candidates in sorted order.

The iterator never processes more nodes than necessary. Each node is pushed and popped exactly once, so the total traversal work is O(n), which makes each next() call amortized O(1). Space usage depends on the height of the tree, typically O(h). This method fits naturally with how binary search trees produce sorted output through in-order traversal and is the most common implementation in production and interviews.

Approach 2: Morris In-order Traversal (Time: O(n), Space: O(1))

Morris traversal removes the need for an auxiliary stack by temporarily modifying the tree structure. For each node, you locate its inorder predecessor and create a temporary threaded link back to the current node. This allows traversal to return after finishing the left subtree without recursion or a stack. When the traversal revisits the predecessor, the temporary link is removed and the algorithm proceeds to the right subtree.

This technique achieves O(1) extra space because it stores traversal state directly in the tree using temporary pointers. Each edge is visited at most twice, keeping the total runtime O(n). However, the tree structure is modified during traversal, which can be undesirable in systems where the tree must remain immutable. Because of this tradeoff, Morris traversal is less common for iterator implementations despite its optimal space usage.

Recommended for interviews: The stack-based controlled in-order traversal is the expected solution. It demonstrates understanding of BST ordering and how to convert recursive traversal into an iterative design using a stack. Morris traversal is a strong follow-up discussion when the interviewer asks how to reduce space from O(h) to O(1), but the stack approach is cleaner and easier to implement correctly under interview constraints.

Approach 1: Approach 1: Using Stack for Controlled In-order Traversal

This approach involves using a stack to simulate the in-order traversal of a binary search tree (BST). The stack is used to keep track of nodes to visit next, starting from the leftmost node (the smallest element). Each time next() is called, the stack pops one node, processes it, and then adds right child nodes to the stack to maintain the in-order sequence. This approach takes advantage of the tree's properties to efficiently traverse it.

The C solution for the BSTIterator uses a stack implemented as a linked list with basic stack operations like push and pop. The constructor initializes the stack with all left children of the root node. The `next` function pops the top of the stack, processes the node, and pushes any right child nodes' left children. The `hasNext` function checks if there are elements in the stack, indicating if another call to `next` is valid.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: The average time complexity is O(1) for next() and hasNext() methods, though next() can take up to O(h) time in the worst case, where h is the height of the tree.
Space Complexity: O(h) due to the depth of the stack, where h is the height of the tree.

Try this approach in the editor →

Approach 2: Approach 2: Morris In-order Traversal

Morris Traversal is an in-order tree traversal technique that doesn't require stack or recursion, thus using O(1) auxiliary space. It temporarily modifies the tree structure to maintain caching pointers, ensuring nodes are revisited as necessary. Once traversal completes, the tree reverts to its original form.

The C solution utilizes Morris traversal to achieve an in-order sequence without extra space. The iterator temporarily modifies the tree with connections called threads to track nodes. As the `next` method works through the tree, each accessed node prints its value and advances by fixing connections afterward. The `hasNext` method merely checks if the tree traversal has completed.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1) on average, with O(n) total time for n nodes.
Space Complexity: O(1) without recourse to stack/recursion.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using Stack for Controlled In-order Traversal

Time Complexity: The average time complexity is O(1) for next() and hasNext() methods, though next() can take up to O(h) time in the worst case, where h is the height of the tree.
Space Complexity: O(h) due to the depth of the stack, where h is the height of the tree.

Approach 2: Morris In-order Traversal

Time Complexity: O(1) on average, with O(n) total time for n nodes.
Space Complexity: O(1) without recourse to stack/recursion.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Stack-based Controlled In-order TraversalO(n) total, O(1) amortized per next()O(h)Standard iterator implementation; clean design for interviews and production
Morris In-order TraversalO(n)O(1)When minimizing auxiliary space and temporary tree modification is acceptable

Video Solution

L50. Binary Search Tree Iterator | BST | O(H) Space • take U forward • 265,780 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Binary Search Tree Iterator easy or hard?
Binary Search Tree Iterator is considered a medium-level problem. The logic relies on understanding in-order traversal and translating recursive traversal into an iterative design with a stack, which is a common pattern in technical interviews.
Binary Search Tree Iterator Python/Java solution
Python and Java implementations typically maintain a stack and a helper function that pushes the left spine of a subtree. next() pops from the stack and processes the node's right subtree, while hasNext() checks if the stack still contains nodes.
How to solve Binary Search Tree Iterator in O(n)?
Perform an in-order traversal while maintaining a stack of nodes representing the path to the next smallest element. Push the leftmost nodes during initialization, pop during next(), and process the right subtree by pushing its left spine. Each node is processed once, resulting in O(n) total time.
What is the best approach for Binary Search Tree Iterator?
The best approach uses a stack to simulate controlled in-order traversal. Initialize the stack with the leftmost path from the root. Each next() call pops the smallest node and pushes the left path of its right subtree. This gives O(1) amortized time per operation and O(h) space where h is the tree height.
Is Binary Search Tree Iterator asked at Google/Amazon/Meta?
Binary Search Tree Iterator appears frequently in interviews at companies that test tree traversal and iterator design patterns. Variants of this problem have been reported in interviews at Amazon, Google, and Meta because it combines BST properties with iterative traversal design.
What data structure is used in Binary Search Tree Iterator?
The primary data structure is a stack that stores nodes along the current traversal path. The stack simulates recursion used in in-order traversal and ensures the iterator always exposes the next smallest element in the BST.
What is the time complexity of Binary Search Tree Iterator?
The total traversal across all operations is O(n) because every node is pushed and popped from the stack exactly once. Individual next() and hasNext() operations run in O(1) amortized time. Space complexity is O(h) where h is the height of the BST.

Ready to solve this problem?

Practice Binary Search Tree Iterator with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Search Tree Iterator II

Next

Binary Tree Inorder Traversal