Binary Search Tree Iterator

Problem Statement

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST. Calling hasNext() will return whether there are any more elements in the iterator.

What to notice first

• In-order traversal yields sorted sequence in BST.
• Stack approach: lazy evaluation, O(1) amortized next().
• Array approach: eager evaluation, O(1) next() but O(n) space.

Examples

Input (BST)	Operation Sequence	Output/Behavior	Explanation
[7,3,15,null,null,9,20]	hasNext(), next(), next(), hasNext(), next()	true, 3, 7, true, 9	In-order: [3, 7, 9, 15, 20]
[1,null,2]	hasNext(), next(), hasNext(), next()	true, 1, true, 2	In-order: [1, 2]
[2,1,3]	next(), next(), next()	1, 2, 3	In-order: [1, 2, 3]

Constraints

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

Design Constraints

• next() and hasNext() should run in O(1) amortized and O(1) time respectively.
• The total number of calls to next() is not more than the number of nodes.

Real-World Applications

Where this pattern appears

• Expression evaluation and parsing
• Browser back button and navigation stack
• Function call stack and recursion
• Bracket matching in compilers

Complexity Comparison

Approach	Time: next()	Space	Best When
Stack (Lazy)	O(1) amortized	O(h)	Space-efficient; iterate large trees
ArrayList (Eager)	O(1)	O(n)	Memory available; all elements needed

Approach 1: Stack (Lazy In-Order)

★ Recommended

Push all left children to stack. When popping, if right exists, push right’s left subtree.

⏱ Time O(1) amortized Each node pushed/popped once 💾 Space O(h) Stack depth = height

Solution Code

Python

binary_search_tree_iterator_stack.py

from typing import Optional


# 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:
    """
    Binary Search Tree Iterator using stack for in-order traversal.
    Implements lazy evaluation: next() O(1) amortized, hasNext() O(1).
    Space: O(h) where h is height
    """

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

    def _push_left(self, node):
        """Push all left nodes onto stack."""
        while node:
            self.stack.append(node)
            node = node.left

    def next(self) -> int:
        """
        Return next smallest element.
        Time: O(1) amortized
        """
        node = self.stack.pop()
        if node.right:
            self._push_left(node.right)
        return node.val

    def hasNext(self) -> bool:
        """
        Check if there are more elements.
        Time: O(1)
        """
        return len(self.stack) > 0


# Test cases
if __name__ == "__main__":
    # Example: [7,3,15,null,null,9,20]
    root = TreeNode(7)
    root.left = TreeNode(3)
    root.right = TreeNode(15)
    root.right.left = TreeNode(9)
    root.right.right = TreeNode(20)

    iterator = BSTIterator(root)
    result = []
    while iterator.hasNext():
        result.append(iterator.next())
    print(result)  # [3, 7, 9, 15, 20]

    # Verify in-order property
    print("In-order traversal correct:", result == sorted(result))

C++

binary_search_tree_iterator_stack.cpp

#include <iostream>
#include <stack>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BSTIterator {
private:
    stack<TreeNode*> st;

    void pushLeft(TreeNode* node) {
        /**Push all left nodes onto stack.*/
        while (node) {
            st.push(node);
            node = node->left;
        }
    }

public:
    BSTIterator(TreeNode* root) {
        /**
         * Binary Search Tree Iterator using stack for in-order traversal.
         * Implements lazy evaluation: next() O(1) amortized, hasNext() O(1).
         * Space: O(h) where h is height
         */
        pushLeft(root);
    }

    int next() {
        /**
         * Return next smallest element.
         * Time: O(1) amortized
         */
        TreeNode* node = st.top();
        st.pop();

        if (node->right) {
            pushLeft(node->right);
        }

        return node->val;
    }

    bool hasNext() {
        /**
         * Check if there are more elements.
         * Time: O(1)
         */
        return !st.empty();
    }
};

// Test cases
int main() {
    // Example: [7,3,15,null,null,9,20]
    TreeNode* root = new TreeNode(7);
    root->left = new TreeNode(3);
    root->right = new TreeNode(15);
    root->right->left = new TreeNode(9);
    root->right->right = new TreeNode(20);

    BSTIterator iterator(root);
    while (iterator.hasNext()) {
        cout << iterator.next() << " ";
    }
    cout << endl;  // 3 7 9 15 20

    return 0;
}

Java

BSTIteratorStack.java

import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
}

class BSTIterator {
    private Stack<TreeNode> stack;

    private void pushLeft(TreeNode node) {
        /**Push all left nodes onto stack.*/
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }

    /**
     * Binary Search Tree Iterator using stack for in-order traversal.
     * Implements lazy evaluation: next() O(1) amortized, hasNext() O(1).
     * Space: O(h) where h is height
     */
    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        pushLeft(root);
    }

    public int next() {
        /**
         * Return next smallest element.
         * Time: O(1) amortized
         */
        TreeNode node = stack.pop();

        if (node.right != null) {
            pushLeft(node.right);
        }

        return node.val;
    }

    public boolean hasNext() {
        /**
         * Check if there are more elements.
         * Time: O(1)
         */
        return !stack.isEmpty();
    }
}

class Main {
    public static void main(String[] args) {
        // Example: [7,3,15,null,null,9,20]
        TreeNode root = new TreeNode(7);
        root.left = new TreeNode(3);
        root.right = new TreeNode(15);
        root.right.left = new TreeNode(9);
        root.right.right = new TreeNode(20);

        BSTIterator iterator = new BSTIterator(root);
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println();  // 3 7 9 15 20
    }
}

JavaScript

binary_search_tree_iterator_stack.js

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Binary Search Tree Iterator using stack for in-order traversal.
 * Implements lazy evaluation: next() O(1) amortized, hasNext() O(1).
 * Space: O(h) where h is height
 */
class BSTIterator {
    constructor(root) {
        this.stack = [];
        this.pushLeft(root);
    }

    pushLeft(node) {
        /**Push all left nodes onto stack.*/
        while (node) {
            this.stack.push(node);
            node = node.left;
        }
    }

    /**
     * Return next smallest element.
     * Time: O(1) amortized
     */
    next() {
        const node = this.stack.pop();

        if (node.right) {
            this.pushLeft(node.right);
        }

        return node.val;
    }

    /**
     * Check if there are more elements.
     * Time: O(1)
     */
    hasNext() {
        return this.stack.length > 0;
    }
}

// Test cases
const root = new TreeNode(7);
root.left = new TreeNode(3);
root.right = new TreeNode(15);
root.right.left = new TreeNode(9);
root.right.right = new TreeNode(20);

const iterator = new BSTIterator(root);
const result = [];
while (iterator.hasNext()) {
    result.push(iterator.next());
}
console.log("In-order traversal:", result);  // [3, 7, 9, 15, 20]

Rust

binary_search_tree_iterator_stack.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * Binary Search Tree Iterator using stack for in-order traversal.
 * Implements lazy evaluation: next() O(1) amortized, hasNext() O(1).
 * Space: O(h) where h is height
 */
pub struct BSTIterator {
    stack: Vec<Rc<RefCell<TreeNode>>>,
}

impl BSTIterator {
    pub fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
        let mut iterator = BSTIterator { stack: Vec::new() };
        iterator.push_left(root);
        iterator
    }

    fn push_left(&mut self, mut node: Option<Rc<RefCell<TreeNode>>>) {
        /**Push all left nodes onto stack.*/
        while let Some(n) = node {
            let n_ref = n.borrow();
            let left = n_ref.left.clone();
            drop(n_ref);
            self.stack.push(n);
            node = left;
        }
    }

    /**
     * Return next smallest element.
     * Time: O(1) amortized
     */
    pub fn next(&mut self) -> i32 {
        if let Some(node) = self.stack.pop() {
            let node_ref = node.borrow();
            let val = node_ref.val;
            let right = node_ref.right.clone();
            drop(node_ref);

            self.push_left(right);
            val
        } else {
            -1
        }
    }

    /**
     * Check if there are more elements.
     * Time: O(1)
     */
    pub fn has_next(&self) -> bool {
        !self.stack.is_empty()
    }
}

fn main() {
    println!("Example 1: BST Iterator using stack");
}

Go

binary_search_tree_iterator_stack.go

package main

import "fmt"

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

/**
 * Binary Search Tree Iterator using stack for in-order traversal.
 * Implements lazy evaluation: next() O(1) amortized, hasNext() O(1).
 * Space: O(h) where h is height
 */
type BSTIterator struct {
    stack []*TreeNode
}

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

func (this *BSTIterator) pushLeft(node *TreeNode) {
    /**Push all left nodes onto stack.*/
    for node != nil {
        this.stack = append(this.stack, node)
        node = node.Left
    }
}

/**
 * Return next smallest element.
 * Time: O(1) amortized
 */
func (this *BSTIterator) Next() int {
    node := this.stack[len(this.stack)-1]
    this.stack = this.stack[:len(this.stack)-1]

    if node.Right != nil {
        this.pushLeft(node.Right)
    }

    return node.Val
}

/**
 * Check if there are more elements.
 * Time: O(1)
 */
func (this *BSTIterator) HasNext() bool {
    return len(this.stack) > 0
}

func main() {
    fmt.Println("Example 1: BST Iterator using stack")
}

Approach 2: ArrayList (Eager Pre-Compute)

alternative

Pre-compute entire in-order traversal into an array. Iterate through array indices.

⏱ Time O(1) Direct index access 💾 Space O(n) Store all elements

Solution Code

Python

binary_search_tree_iterator_arraylist.py

from typing import Optional


# 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:
    """
    Binary Search Tree Iterator using pre-computed ArrayList.
    Stores all in-order elements upfront.
    Space: O(n), next() O(1), hasNext() O(1)
    """

    def __init__(self, root: Optional[TreeNode]):
        self.arr = []
        self.index = 0
        self._inorder(root)

    def _inorder(self, node):
        """Pre-compute in-order traversal into array."""
        if not node:
            return
        self._inorder(node.left)
        self.arr.append(node.val)
        self._inorder(node.right)

    def next(self) -> int:
        """
        Return next smallest element.
        Time: O(1)
        """
        val = self.arr[self.index]
        self.index += 1
        return val

    def hasNext(self) -> bool:
        """
        Check if there are more elements.
        Time: O(1)
        """
        return self.index < len(self.arr)


# Test cases
if __name__ == "__main__":
    # Example: [7,3,15,null,null,9,20]
    root = TreeNode(7)
    root.left = TreeNode(3)
    root.right = TreeNode(15)
    root.right.left = TreeNode(9)
    root.right.right = TreeNode(20)

    iterator = BSTIterator(root)
    result = []
    while iterator.hasNext():
        result.append(iterator.next())
    print(result)  # [3, 7, 9, 15, 20]

    # Verify in-order property
    print("In-order traversal correct:", result == sorted(result))

C++

binary_search_tree_iterator_arraylist.cpp

#include <iostream>
#include <vector>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BSTIterator {
private:
    vector<int> arr;
    int index = 0;

    void inorder(TreeNode* node) {
        /**Pre-compute in-order traversal into array.*/
        if (!node) return;

        inorder(node->left);
        arr.push_back(node->val);
        inorder(node->right);
    }

public:
    BSTIterator(TreeNode* root) {
        /**
         * Binary Search Tree Iterator using pre-computed vector.
         * Stores all in-order elements upfront.
         * Space: O(n), next() O(1), hasNext() O(1)
         */
        inorder(root);
    }

    int next() {
        /**
         * Return next smallest element.
         * Time: O(1)
         */
        return arr[index++];
    }

    bool hasNext() {
        /**
         * Check if there are more elements.
         * Time: O(1)
         */
        return index < arr.size();
    }
};

// Test cases
int main() {
    // Example: [7,3,15,null,null,9,20]
    TreeNode* root = new TreeNode(7);
    root->left = new TreeNode(3);
    root->right = new TreeNode(15);
    root->right->left = new TreeNode(9);
    root->right->right = new TreeNode(20);

    BSTIterator iterator(root);
    while (iterator.hasNext()) {
        cout << iterator.next() << " ";
    }
    cout << endl;  // 3 7 9 15 20

    return 0;
}

Java

BSTIteratorArrayList.java

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
}

class BSTIterator {
    private List<Integer> arr;
    private int index = 0;

    private void inorder(TreeNode node) {
        /**Pre-compute in-order traversal into list.*/
        if (node == null) return;

        inorder(node.left);
        arr.add(node.val);
        inorder(node.right);
    }

    /**
     * Binary Search Tree Iterator using pre-computed ArrayList.
     * Stores all in-order elements upfront.
     * Space: O(n), next() O(1), hasNext() O(1)
     */
    public BSTIterator(TreeNode root) {
        arr = new ArrayList<>();
        inorder(root);
    }

    public int next() {
        /**
         * Return next smallest element.
         * Time: O(1)
         */
        return arr.get(index++);
    }

    public boolean hasNext() {
        /**
         * Check if there are more elements.
         * Time: O(1)
         */
        return index < arr.size();
    }
}

class Main {
    public static void main(String[] args) {
        // Example: [7,3,15,null,null,9,20]
        TreeNode root = new TreeNode(7);
        root.left = new TreeNode(3);
        root.right = new TreeNode(15);
        root.right.left = new TreeNode(9);
        root.right.right = new TreeNode(20);

        BSTIterator iterator = new BSTIterator(root);
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println();  // 3 7 9 15 20
    }
}

JavaScript

binary_search_tree_iterator_arraylist.js

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Binary Search Tree Iterator using pre-computed array.
 * Stores all in-order elements upfront.
 * Space: O(n), next() O(1), hasNext() O(1)
 */
class BSTIterator {
    constructor(root) {
        this.arr = [];
        this.index = 0;
        this.inorder(root);
    }

    inorder(node) {
        /**Pre-compute in-order traversal into array.*/
        if (!node) return;

        this.inorder(node.left);
        this.arr.push(node.val);
        this.inorder(node.right);
    }

    /**
     * Return next smallest element.
     * Time: O(1)
     */
    next() {
        return this.arr[this.index++];
    }

    /**
     * Check if there are more elements.
     * Time: O(1)
     */
    hasNext() {
        return this.index < this.arr.length;
    }
}

// Test cases
const root = new TreeNode(7);
root.left = new TreeNode(3);
root.right = new TreeNode(15);
root.right.left = new TreeNode(9);
root.right.right = new TreeNode(20);

const iterator = new BSTIterator(root);
const result = [];
while (iterator.hasNext()) {
    result.push(iterator.next());
}
console.log("In-order traversal:", result);  // [3, 7, 9, 15, 20]

Rust

binary_search_tree_iterator_arraylist.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * Binary Search Tree Iterator using pre-computed Vec.
 * Stores all in-order elements upfront.
 * Space: O(n), next() O(1), hasNext() O(1)
 */
pub struct BSTIterator {
    arr: Vec<i32>,
    index: usize,
}

impl BSTIterator {
    pub fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
        let mut arr = Vec::new();
        BSTIterator::inorder(root, &mut arr);
        BSTIterator { arr, index: 0 }
    }

    fn inorder(node: Option<Rc<RefCell<TreeNode>>>, arr: &mut Vec<i32>) {
        /**Pre-compute in-order traversal into array.*/
        if let Some(n) = node {
            let node_ref = n.borrow();
            let left = node_ref.left.clone();
            let val = node_ref.val;
            let right = node_ref.right.clone();
            drop(node_ref);

            Self::inorder(left, arr);
            arr.push(val);
            Self::inorder(right, arr);
        }
    }

    /**
     * Return next smallest element.
     * Time: O(1)
     */
    pub fn next(&mut self) -> i32 {
        let val = self.arr[self.index];
        self.index += 1;
        val
    }

    /**
     * Check if there are more elements.
     * Time: O(1)
     */
    pub fn has_next(&self) -> bool {
        self.index < self.arr.len()
    }
}

fn main() {
    println!("Example 1: BST Iterator using ArrayList");
}

Go

binary_search_tree_iterator_arraylist.go

package main

import "fmt"

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

/**
 * Binary Search Tree Iterator using pre-computed slice.
 * Stores all in-order elements upfront.
 * Space: O(n), next() O(1), hasNext() O(1)
 */
type BSTIterator struct {
    arr   []int
    index int
}

func Constructor(root *TreeNode) BSTIterator {
    iterator := BSTIterator{arr: []int{}, index: 0}
    iterator.inorder(root)
    return iterator
}

func (this *BSTIterator) inorder(node *TreeNode) {
    /**Pre-compute in-order traversal into array.*/
    if node == nil {
        return
    }

    this.inorder(node.Left)
    this.arr = append(this.arr, node.Val)
    this.inorder(node.Right)
}

/**
 * Return next smallest element.
 * Time: O(1)
 */
func (this *BSTIterator) Next() int {
    val := this.arr[this.index]
    this.index++
    return val
}

/**
 * Check if there are more elements.
 * Time: O(1)
 */
func (this *BSTIterator) HasNext() bool {
    return this.index < len(this.arr)
}

func main() {
    fmt.Println("Example 1: BST Iterator using ArrayList")
}

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

binary_search_tree_iterator_space_optimized.py

"""
Solution for Binary Search Tree Iterator
"""

def solve():
    """Implementation for approach 3 of Binary Search Tree Iterator"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

binary_search_tree_iterator_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Binary Search Tree Iterator
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

BinarySearchTreeIteratorSpaceOptimized.java

/**
 * Solution for Binary Search Tree Iterator
 * Approach 3
 */
public class BinarySearchTreeIteratorSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

binary_search_tree_iterator_space_optimized.js

/**
 * Solution for Binary Search Tree Iterator
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

binary_search_tree_iterator_space_optimized.rs

/// Solution for Binary Search Tree Iterator
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

binary_search_tree_iterator_space_optimized.go

package main

import "fmt"

// Solution for Binary Search Tree Iterator
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Binary Tree Inorder Traversal ↗ Easy #94
• Reorder List ↗ Medium #143
• Closest Binary Search Tree Value ↗ Easy #270

Interview Tips

Key trade-offs to discuss

• Time vs. space trade-offs between approaches
• Handling edge cases (empty inputs, single elements, duplicates)
• Optimization opportunities and when they matter
• Follow-up variations and constraint changes