Skip to main content
Talentd

Binary Search Tree Iterator II - Solution & Explanation

MediumPremiumFree on FleetCodeStackTreeDesignBinary Search Tree11 min readAsked at: Meta
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.
  • boolean hasPrev() Returns true if there exists a number in the traversal to the left of the pointer, otherwise returns false.
  • int prev() Moves the pointer to the left, 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() and prev() calls will always be valid. That is, there will be at least a next/previous number in the in-order traversal when next()/prev() is called.

 

Example 1:

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

Explanation
// The underlined element is where the pointer currently is.
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); // state is   [3, 7, 9, 15, 20]
bSTIterator.next(); // state becomes [3, 7, 9, 15, 20], return 3
bSTIterator.next(); // state becomes [3, 7, 9, 15, 20], return 7
bSTIterator.prev(); // state becomes [3, 7, 9, 15, 20], return 3
bSTIterator.next(); // state becomes [3, 7, 9, 15, 20], return 7
bSTIterator.hasNext(); // return true
bSTIterator.next(); // state becomes [3, 7, 9, 15, 20], return 9
bSTIterator.next(); // state becomes [3, 7, 9, 15, 20], return 15
bSTIterator.next(); // state becomes [3, 7, 9, 15, 20], return 20
bSTIterator.hasNext(); // return false
bSTIterator.hasPrev(); // return true
bSTIterator.prev(); // state becomes [3, 7, 9, 15, 20], return 15
bSTIterator.prev(); // state becomes [3, 7, 9, 15, 20], return 9

 

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, next, hasPrev, and prev.

 

Follow up: Could you solve the problem without precalculating the values of the tree?

Approach Overview

Problem Overview: Design an iterator for a Binary Search Tree (BST) that supports both forward and backward traversal. Besides the usual next() and hasNext(), the iterator must also implement prev() and hasPrev(), allowing you to move one step back in the in-order traversal sequence.

Approach 1: In-order Traversal + Array (O(n) time, O(n) space)

The simplest approach is to flatten the BST using an in-order traversal and store the result in an array. Since in-order traversal of a Binary Search Tree produces sorted values, the iterator becomes a simple index moving forward or backward through that array. Build the array once during initialization with a DFS traversal of the binary tree. Maintain an index pointer that moves right for next() and left for prev().

This approach makes every iterator operation constant time because it only updates an index. The trade-off is memory usage: you store all n nodes upfront. This solution is straightforward, easy to implement, and performs well when the tree size is manageable.

Approach 2: Lazy In-order Traversal with Stack + History (O(1) amortized time, O(h + k) space)

A more memory-efficient design performs in-order traversal lazily using a stack. The stack stores the traversal state, pushing left children until the smallest node is reached. Each call to next() processes the stack similarly to a standard BST iterator. To support prev(), maintain a list of already visited values and an index pointing to the current position. If the user moves backward, simply decrement the index. If moving forward beyond visited elements, resume traversal from the stack.

This hybrid structure combines a traversal stack with a history list. The stack depth is at most the tree height h, while the history grows to the number of visited nodes k. Each node is pushed and popped at most once, giving amortized O(1) time per operation. Compared with the full-array approach, it avoids computing the entire traversal upfront.

Recommended for interviews: The lazy traversal with a stack and history list demonstrates stronger understanding of iterator design and tree traversal. The array approach is perfectly valid and quick to implement, but interviewers often prefer the stack-based iterator because it processes nodes on demand and mirrors real iterator patterns used in system design.

Solution

We can use in-order traversal to store the values of all nodes in the binary search tree into an array nums, and then use the array to implement the iterator. We define a pointer i, initially i = -1, which points to an element in the array nums. Each time we call next(), we add 1 to the value of i and return nums[i]; each time we call prev(), we subtract 1 from the value of i and return nums[i].

In terms of time complexity, initializing the iterator requires O(n) time, where n is the number of nodes in the binary search tree. Each call to next() and prev() requires O(1) time. In terms of space complexity, we need O(n) space to store the values of all nodes in the binary search tree.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
In-order Traversal + ArrayO(n) preprocessing, O(1) per operationO(n)Best when simplicity matters and memory for storing all nodes is acceptable
Lazy In-order Traversal with Stack + HistoryO(1) amortized per operationO(h + k)Preferred for interview discussions and when avoiding full traversal upfront

Video Solution

1586. Binary Search Tree Iterator II (Leetcode Medium) • Programming Live with Larry • 341 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Binary Search Tree Iterator II easy or hard?
Binary Search Tree Iterator II is generally rated Medium difficulty. The main challenge is extending a standard BST iterator to support backward movement efficiently without recomputing traversal each time.
Binary Search Tree Iterator II Python/Java solution
Implement the iterator by either precomputing an in-order array or performing lazy traversal with a stack. Python, Java, C++, Go, and TypeScript implementations typically maintain a pointer index and helper functions for pushing left nodes onto the stack.
How to solve Binary Search Tree Iterator II in O(n)?
Perform a full in-order traversal of the BST and store values in an array. Maintain a pointer that moves forward for next() and backward for prev(). The traversal costs O(n) time and space, while each iterator call becomes a constant-time index update.
What is the best approach for Binary Search Tree Iterator II?
The most practical approach uses lazy in-order traversal with a stack and a history list. The stack maintains traversal state while the history stores visited nodes so prev() can move backward. Each operation runs in O(1) amortized time with O(h + k) space, where h is tree height and k is visited nodes.
Is Binary Search Tree Iterator II asked at Google/Amazon/Meta?
BST iterator design problems are common in interviews at companies like Amazon, Google, and Meta because they test tree traversal, stack usage, and iterator design. Variants of BST Iterator I and II frequently appear in coding interviews and online assessments.
What data structure is used in Binary Search Tree Iterator II?
The core data structures are a stack for in-order traversal and an array or list to store visited values. The stack maintains traversal state for the BST, while the list enables constant-time backward navigation for prev().
What is the time complexity of Binary Search Tree Iterator II?
Using an in-order array, preprocessing takes O(n) time and each iterator operation runs in O(1). With the stack-based lazy traversal, next() and prev() both run in O(1) amortized time because each node is pushed and popped from the stack at most once.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Binary Search Tree Iterator