Binary Search Tree Iterator solution and explanation
Google
9 more videos on this problem
L50. Binary Search Tree Iterator | BST | O(H) Spacetake U forward · 14:00 · 265K views
Binary Search Tree Iterator - Leetcode 173 - PythonNeetCode · 12:47 · 60K views
Binary Search Tree Iterator | Live Coding with Explanation | Leetcode - 173Algorithms Made Easy · 5:59 · 8K views
Binary Search Tree Iterator | Leetcode 173 | Google Apple Facebook Amazon Microsoft | BSTNaresh Gupta · 9:14 · 3K views
Binary Search Tree Iterator (Leetcode #173)Prakash V · 8:40 · 2K views
LeetCode 173. Binary Search Tree IteratorHappy Coding · 12:53 · 1K views
Binary Search Tree Iterator | Leetcode 173 | Binary Search Tree 🔥🔥 | Live coding sessionCoding Decoded · 10:17 · 1K views
LeetCode 173. Binary Search Tree Iterator | JSer - JavaScript & AlgorithmJSer · 8:01 · 334 views
Binary Search Tree Iterator | Leetcode 173 | THANK YOU FOR 500 SUBSCRIBERS :) !!!!!Super Lazy Coder · 15:53 · 179 views
LEETCODE 173: STACK ALL LEFT NODES PATTERN : BST (BINARY SEARCH TREE) ITERATOR : C++ SOLUTION.leetcode blind 75 · 5:34 · 133 views
The problem
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 theBSTIteratorclass. Therootof 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()Returnstrueif there exists a number in the traversal to the right of the pointer, otherwise returnsfalse.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
105calls will be made tohasNext, andnext.
Follow up:
- Could you implement
next()andhasNext()to run in averageO(1)time and useO(h)memory, wherehis 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.
class BSTIterator:
def __init__(self, root: TreeNode):
self.stack = []
self._push_left_nodes(root)
def _push_left_nodes(self, node: TreeNode):
while node:
self.stack.append(node)
node = node.left
def next(self) -> int:
node = self.stack.pop()
result = node.val
if node.right:
self._push_left_nodes(node.right)
return result
def hasNext(self) -> bool:
return len(self.stack) > 0import java.util.Stack;
class BSTIterator {
private Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack<>();
pushLeftNodes(root);
}
private void pushLeftNodes(TreeNode node) {
while (node != null) {
stack.push(node);
node = node.left;
}
}
public boolean hasNext() {
return !stack.isEmpty();
}
public int next() {
TreeNode node = stack.pop();
int result = node.val;
if (node.right != null) {
pushLeftNodes(node.right);
}
return result;
}
}#include <stack>
class BSTIterator {
public:
BSTIterator(TreeNode* root) {
pushLeftNodes(root);
}
bool hasNext() {
return !stk.empty();
}
int next() {
TreeNode* node = stk.top();
stk.pop();
int result = node->val;
if (node->right) {
pushLeftNodes(node->right);
}
return result;
}
private:
std::stack<TreeNode*> stk;
void pushLeftNodes(TreeNode* node) {
while (node) {
stk.push(node);
node = node->left;
}
}
};class BSTIterator {
constructor(root) {
this.stack = [];
this._pushLeftNodes(root);
}
_pushLeftNodes(node) {
while (node !== null) {
this.stack.push(node);
node = node.left;
}
}
next() {
const node = this.stack.pop();
const result = node.val;
if (node.right !== null) {
this._pushLeftNodes(node.right);
}
return result;
}
hasNext() {
return this.stack.length > 0;
}
}#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// TreeNode structure definition
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// Stack structure definition
typedef struct Stack {
struct TreeNode* node;
struct Stack* next;
} Stack;
// BSTIterator structure definition
typedef struct {
Stack* top;
} BSTIterator;
// Function to create a new stack node
Stack* newStackNode(struct TreeNode* node) {
Stack* stackNode = malloc(sizeof(Stack));
stackNode->node = node;
stackNode->next = NULL;
return stackNode;
}
// Function to push a node to the stack
void push(Stack** topRef, struct TreeNode* node) {
Stack* stackNode = newStackNode(node);
stackNode->next = *topRef;
*topRef = stackNode;
}
// Function to pop a node from the stack
struct TreeNode* pop(Stack** topRef) {
if (*topRef == NULL) return NULL;
Stack* top = *topRef;
*topRef = top->next;
struct TreeNode* node = top->node;
free(top);
return node;
}
// Function to push all left children of a node to the stack
void pushLeftNodes(Stack** stack, struct TreeNode* node) {
while (node != NULL) {
push(stack, node);
node = node->left;
}
}
// Constructor for BSTIterator
BSTIterator* bSTIteratorCreate(struct TreeNode* root) {
BSTIterator* iterator = malloc(sizeof(BSTIterator));
iterator->top = NULL;
pushLeftNodes(&iterator->top, root);
return iterator;
}
// Check if there's a next node
bool bSTIteratorHasNext(BSTIterator* iterator) {
return iterator->top != NULL;
}
// Return the next smallest node
int bSTIteratorNext(BSTIterator* iterator) {
struct TreeNode* node = pop(&iterator->top);
int result = node->val;
if (node->right != NULL) {
pushLeftNodes(&iterator->top, node->right);
}
return result;
}
// Destructor
void bSTIteratorFree(BSTIterator* iterator) {
while (iterator->top != NULL) {
pop(&iterator->top);
}
free(iterator);
}using System.Collections.Generic;
public class BSTIterator {
private Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack<TreeNode>();
PushLeftNodes(root);
}
private void PushLeftNodes(TreeNode node) {
while (node != null) {
stack.Push(node);
node = node.left;
}
}
public int Next() {
TreeNode node = stack.Pop();
int result = node.val;
if (node.right != null) {
PushLeftNodes(node.right);
}
return result;
}
public bool HasNext() {
return stack.Count > 0;
}
}The Python solution uses a list to simulate the stack. The iterator's constructor pushes all left children of the root into the stack. next() gives the next smallest number by popping the stack and potentially adding a right child’s children if they exist. hasNext() checks if the stack is empty to determine the presence of further elements.
Time Complexity: O(1) on average per `next` and `hasNext`, though `next` may occasionally incur O(h) in the worst case.
Space Complexity: O(h), tied to the stack depth.
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.
class BSTIterator:
def __init__(self, root: TreeNode):
self.current = root
def hasNext(self) -> bool:
return self.current is not None
def next(self) -> int:
result = 0
while self.current:
if self.current.left is None:
result = self.current.val
self.current = self.current.right
break
else:
pred = self.findPredecessor(self.current)
if pred.right is None:
pred.right = self.current
self.current = self.current.left
else:
pred.right = None
result = self.current.val
self.current = self.current.right
break
return result
def findPredecessor(self, node: TreeNode) -> TreeNode:
pred = node.left
while pred.right is not None and pred.right != node:
pred = pred.right
return predpublic class BSTIterator {
private TreeNode current;
public BSTIterator(TreeNode root) {
current = root;
}
public boolean hasNext() {
return current != null;
}
public int next() {
int result = 0;
while (current != null) {
if (current.left == null) {
result = current.val;
current = current.right;
break;
} else {
TreeNode pred = findPredecessor(current);
if (pred.right == null) {
pred.right = current;
current = current.left;
} else {
pred.right = null;
result = current.val;
current = current.right;
break;
}
}
}
return result;
}
private TreeNode findPredecessor(TreeNode node) {
TreeNode pred = node.left;
while (pred.right != null && pred.right != node) {
pred = pred.right;
}
return pred;
}
}class BSTIterator {
public:
BSTIterator(TreeNode* root) : current(root) {}
bool hasNext() {
return current != nullptr;
}
int next() {
int result = 0;
while (current) {
if (current->left == nullptr) {
result = current->val;
current = current->right;
break;
} else {
TreeNode* pred = findPredecessor(current);
if (pred->right == nullptr) {
pred->right = current;
current = current->left;
} else {
pred->right = nullptr;
result = current->val;
current = current->right;
break;
}
}
}
return result;
}
private:
TreeNode* current;
TreeNode* findPredecessor(TreeNode* node) {
TreeNode* pred = node->left;
while (pred->right && pred->right != node) {
pred = pred->right;
}
return pred;
}
};class BSTIterator {
constructor(root) {
this.current = root;
}
hasNext() {
return this.current !== null;
}
next() {
let result = 0;
while (this.current !== null) {
if (this.current.left === null) {
result = this.current.val;
this.current = this.current.right;
break;
} else {
let pred = this.findPredecessor(this.current);
if (pred.right === null) {
pred.right = this.current;
this.current = this.current.left;
} else {
pred.right = null;
result = this.current.val;
this.current = this.current.right;
break;
}
}
}
return result;
}
findPredecessor(node) {
let pred = node.left;
while (pred.right !== null && pred.right !== node) {
pred = pred.right;
}
return pred;
}
}#include <stdlib.h>
#include <stdbool.h>
// TreeNode structure definition
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// BSTIterator structure definition
typedef struct {
struct TreeNode* current;
} BSTIterator;
// Constructor for BSTIterator
BSTIterator* bSTIteratorCreate(struct TreeNode* root) {
BSTIterator* iterator = (BSTIterator*)malloc(sizeof(BSTIterator));
iterator->current = root;
return iterator;
}
// Function to find the rightmost node in the left subtree
struct TreeNode* findPredecessor(struct TreeNode* node) {
struct TreeNode* pred = node->left;
while (pred->right && pred->right != node) {
pred = pred->right;
}
return pred;
}
// Check if there's a next node
bool bSTIteratorHasNext(BSTIterator* iterator) {
return iterator->current != NULL;
}
// Return the next smallest node
int bSTIteratorNext(BSTIterator* iterator) {
int result = 0;
while (iterator->current) {
if (iterator->current->left == NULL) {
result = iterator->current->val;
iterator->current = iterator->current->right;
return result;
}
struct TreeNode* pred = findPredecessor(iterator->current);
if (pred->right == NULL) {
pred->right = iterator->current;
iterator->current = iterator->current->left;
} else {
pred->right = NULL;
result = iterator->current->val;
iterator->current = iterator->current->right;
return result;
}
}
return result; // This line may not be necessary because iteration always has next
}
// Destructor
void bSTIteratorFree(BSTIterator* iterator) {
free(iterator);
}public class BSTIterator {
private TreeNode current;
public BSTIterator(TreeNode root) {
current = root;
}
public bool HasNext() {
return current != null;
}
public int Next() {
int result = 0;
while (current != null) {
if (current.left == null) {
result = current.val;
current = current.right;
break;
} else {
TreeNode pred = FindPredecessor(current);
if (pred.right == null) {
pred.right = current;
current = current.left;
} else {
pred.right = null;
result = current.val;
current = current.right;
break;
}
}
}
return result;
}
private TreeNode FindPredecessor(TreeNode node) {
TreeNode pred = node.left;
while (pred.right != null && pred.right != node) {
pred = pred.right;
}
return pred;
}
}Using Morris Traversal in Python effects node examination in ascending form, enforcing necessary temporary link repairs afterward. `hasNext` confirms ongoing traversal potential, ensuring comprehensive exploration with bounded memory usage.
Time Complexity: O(1) per node visit, finalizing within O(n) for all nodes.
Space Complexity: Minimal O(1), representing direct node access.
Approach 3: Default Approach
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
class BSTIterator {
private data: number[];
private index: number;
constructor(root: TreeNode | null) {
this.index = 0;
this.data = [];
const dfs = (root: TreeNode | null) => {
if (root == null) {
return;
}
const { val, left, right } = root;
dfs(left);
this.data.push(val);
dfs(right);
};
dfs(root);
}
next(): number {
return this.data[this.index++];
}
hasNext(): boolean {
return this.index < this.data.length;
}
}
/**
* 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()
*//**
* 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 {
var stack []*TreeNode
for ; root != nil; root = root.Left {
stack = append(stack, root)
}
return BSTIterator{
stack: stack,
}
}
func (this *BSTIterator) Next() int {
cur := this.stack[len(this.stack)-1]
this.stack = this.stack[:len(this.stack)-1]
for node := cur.Right; node != nil; node = node.Left {
this.stack = append(this.stack, node)
}
return cur.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();
*/// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
struct BSTIterator {
vals: Vec<i32>,
index: usize,
}
use std::cell::RefCell;
use std::rc::Rc;
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl BSTIterator {
fn inorder(root: &Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>) {
if let Some(node) = root {
let node = node.as_ref().borrow();
Self::inorder(&node.left, res);
res.push(node.val);
Self::inorder(&node.right, res);
}
}
fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
let mut vals = vec![];
Self::inorder(&root, &mut vals);
BSTIterator { vals, index: 0 }
}
fn next(&mut self) -> i32 {
self.index += 1;
self.vals[self.index - 1]
}
fn has_next(&self) -> bool {
self.index != self.vals.len()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Stack for Controlled In-order Traversal | Time Complexity: |
| Approach 2: Morris In-order Traversal | Time Complexity: |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-based Controlled In-order Traversal | O(n) total, O(1) amortized per next() | O(h) | Standard iterator implementation; clean design for interviews and production |
| Morris In-order Traversal | O(n) | O(1) | When minimizing auxiliary space and temporary tree modification is acceptable |
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.