Binary Search Tree Iterator

Med

#0173Time: Constructor: O(N), `next()`: O(1), `hasNext()`: O(1), where N is the number of nodes in the tree.Space: O(N), to store the values of all N nodes in the list.2 companies

Patterns

Design Iterator

Data structures

Stack Tree Binary Tree Binary Search Tree

Companies

LinkedIn Media.net

Prompt

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, 10⁵].
0 <= Node.val <= 10⁶
At most 10⁵ 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?

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves performing a full in-order traversal of the BST during the initialization of the iterator. All the node values are stored in a dynamic array or list in their sorted, in-order sequence. The iterator then simply traverses this pre-computed list.

Algorithm

In the constructor, create an empty list nodes.
Perform a recursive in-order traversal of the tree.
During the traversal, add each node's value to the nodes list.
Initialize an index to 0.
For next(), return nodes.get(index) and then increment index.
For hasNext(), return true if index is less than the size of nodes, false otherwise.

Walkthrough

The core idea is to convert the tree traversal problem into a simple list iteration problem.

Constructor BSTIterator(TreeNode root):

Initialize an empty list, for example, an ArrayList<Integer>.
Implement a helper function, typically recursive, to perform an in-order traversal (Left -> Root -> Right).
Call this helper function starting from the root to populate the list with all node values.
Initialize an index or pointer to the beginning of the list (e.g., index = 0).

hasNext() method:

This method simply checks if the current index is within the bounds of the list (i.e., index < list.size()).

next() method:

It retrieves the element at the current index from the list.
Increments the index to point to the next element.
Returns the retrieved value.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class BSTIterator {17    private List<Integer> nodes;18    private int index;19 20    public BSTIterator(TreeNode root) {21        this.nodes = new ArrayList<>();22        this.index = 0;23        this._inorder(root);24    }25 26    private void _inorder(TreeNode root) {27        if (root == null) {28            return;29        }30        _inorder(root.left);31        this.nodes.add(root.val);32        _inorder(root.right);33    }34 35    public int next() {36        return this.nodes.get(this.index++);37    }38 39    public boolean hasNext() {40        return this.index < this.nodes.size();41    }42}

Complexity

Time

Constructor: O(N), `next()`: O(1), `hasNext()`: O(1), where N is the number of nodes in the tree.

Space

O(N), to store the values of all N nodes in the list.

Trade-offs

Pros

Simple to understand and implement.
The next() and hasNext() operations are very fast (true O(1)) after the initial setup.

Cons

High space complexity of O(N), which can be significant for large trees.
The constructor performs O(N) work upfront, which is inefficient if the iterator is only used to get a few elements.

This approach simulates the in-order traversal iteratively using a stack, processing nodes only when they are requested. This avoids the need to store all nodes at once, leading to much better space complexity. It's often called a 'lazy' approach because it does just enough work for each next() call.

Algorithm

Initialize a stack in the constructor.
Create a helper function _leftmostInorder(node) that pushes a node and all its left children onto the stack.
Call _leftmostInorder(root) in the constructor to initialize the stack with the path to the smallest element.
For hasNext(), check if the stack is empty.
For next():
- Pop a node from the stack. This is the current smallest node.
- If the popped node has a right child, call _leftmostInorder on its right child to prepare for the next call.
- Return the value of the popped node.

Walkthrough

Instead of pre-computing the entire traversal, we use a stack to keep track of the path to the next smallest node. This is analogous to how a recursive in-order traversal uses the call stack.

Constructor BSTIterator(TreeNode root):

Initialize an empty Stack<TreeNode>.
To prepare for the first next() call (which should return the smallest element), we must find the leftmost node. We do this by pushing the root and all its subsequent left children onto the stack.

hasNext() method:

The iterator has a next element if and only if the stack is not empty.

next() method:

The node at the top of the stack is the next smallest element. Pop this node from the stack.
Let the popped node be currentNode.
After processing currentNode, the next element in the in-order sequence is the smallest element in currentNode's right subtree.
If currentNode has a right child, push that right child and all of its left descendants onto the stack. This sets up the stack for the subsequent next() call.
Return the value of currentNode.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class BSTIterator {17    private Stack<TreeNode> stack;18 19    public BSTIterator(TreeNode root) {20        this.stack = new Stack<>();21        // Push all the left nodes of the root onto the stack22        this._leftmostInorder(root);23    }24 25    private void _leftmostInorder(TreeNode root) {26        while (root != null) {27            this.stack.push(root);28            root = root.left;29        }30    }31 32    /** @return the next smallest number */33    public int next() {34        // The top of the stack is the next smallest node35        TreeNode topmostNode = this.stack.pop();36 37        // If the popped node has a right child, we need to38        // find the smallest node in its right subtree.39        if (topmostNode.right != null) {40            this._leftmostInorder(topmostNode.right);41        }42 43        return topmostNode.val;44    }45 46    /** @return whether we have a next smallest number */47    public boolean hasNext() {48        return !this.stack.isEmpty();49    }50}

Complexity

Time

`hasNext()`: O(1). `next()`: Amortized O(1). While a single call can take up to O(h) in the worst case, each node is pushed and popped exactly once over the entire traversal, making the average time O(1).

Space

O(h), where h is the height of the tree. The stack stores at most h nodes, which corresponds to the longest path from the root to a leaf.

Trade-offs

Pros

Optimal space complexity of O(h), satisfying the follow-up question.
Lazy evaluation: work is distributed across next() calls, which is efficient if the full tree is not traversed.
Average O(1) time complexity for next() and hasNext().

Cons

The implementation is more complex than the flattening approach.
The time complexity for a single next() call is not strictly O(1) and can be O(h) in some cases.

Solutions

Solution

1import java.util.ArrayList ; import java.util.Collections ; import java.util.List ; import java.util.Stack ; public class Binary_Search_Tree_Iterator { /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class BSTIterator { Stack < TreeNode > sk ; // @note:@memorize: important feature, min is always going left branch to leaf public BSTIterator ( TreeNode root ) { sk = new Stack <>(); // all the way to leftmost leaf while ( root != null ) { sk . push ( root ); root = root . left ; } } /** @return whether we have a next smallest number */ public boolean hasNext () { return ! sk . isEmpty (); } /** @return the next smallest number */ public int next () { TreeNode minNode = sk . pop (); TreeNode current = minNode ; // update stack, possible next time min is frmo its right-then-left branch if ( current . right != null ) { current = current . right ; // same logic as in constructor while ( current != null ) { sk . push ( current . left ); current = current . left ; } } return minNode . val ; } } /** * Your BSTIterator will be called like this: * BSTIterator i = new BSTIterator(root); * while (i.hasNext()) v[f()] = i.next(); */ } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class BSTIterator { private Deque < TreeNode > stack = new LinkedList <>(); public BSTIterator ( TreeNode root ) { for (; root != null ; root = root . left ) { stack . offerLast ( root ); } } public int next () { TreeNode cur = stack . pollLast (); for ( TreeNode node = cur . right ; node != null ; node = node . left ) { stack . offerLast ( node ); } return cur . val ; } public boolean hasNext () { return ! stack . isEmpty (); } } /** * Your BSTIterator object will be instantiated and called as such: * BSTIterator obj = new BSTIterator(root); * int param_1 = obj.next(); * boolean param_2 = obj.hasNext(); */

1/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root */ var BSTIterator =2  function (root) {3    this.stack = [];4    for (; root != null; root = root.left) {5      this.stack.push(root);6    }7  };8/** * @return {number} */ BSTIterator.prototype.next = function () {9  let cur = this.stack.pop();10  let node = cur.right;11  for (; node != null; node = node.left) {12    this.stack.push(node);13  }14  return cur.val;15};16/** * @return {boolean} */ BSTIterator.prototype.hasNext = function () {17  return this.stack.length > 0;18}; /** * Your BSTIterator object will be instantiated and called as such: * var obj = new BSTIterator(root) * var param_1 = obj.next() * var param_2 = obj.hasNext() */

1# 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 class BSTIterator : def __init__ ( self , root : TreeNode ): self . stack = [] self . _leftmost_inorder ( root ) def _leftmost_inorder ( self , node ): while node : self . stack . append ( node ) node = node . left def next ( self ) -> int : cur = self . stack . pop () node = cur . right self . _leftmost_inorder ( node ) return cur . 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() ############# # 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 class BSTIterator : def __init__ ( self , root : TreeNode ): self . stack = [] while root : self . stack . append ( root ) root = root . left def next ( self ) -> int : cur = self . stack . pop () node = cur . right while node : # deplicated while block self . stack . append ( node ) node = node . left return cur . 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()

1// OJ: https://leetcode.com/problems/binary-search-tree-iterator/ // Time: O(1) amortized // Space: O(H) class BSTIterator { private: stack < TreeNode *> s ; void pushNodes ( TreeNode * node ) { while ( node ) { s . push ( node ); node = node -> left ; } } public: BSTIterator ( TreeNode * root ) { pushNodes ( root ); } int next () { auto node = s . top (); s . pop (); pushNodes ( node -> right ); return node -> val ; } bool hasNext () { return s . size (); } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem