Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Binary Search Tree Iterator

MEDIUMProblemSolveExternal Links

Description

Design and implement a BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST).

Your class should support the following operations:

  • BSTIterator(TreeNode root) — Initializes the iterator with the root of a BST. The internal pointer should be positioned before the smallest element in the tree.
  • int next() — Moves the pointer to the next element in the in-order sequence and returns its value. Since the pointer starts before the first element, the first call to next() returns the smallest value in the BST.
  • boolean hasNext() — Returns true if there are still elements to visit in the in-order sequence, and false otherwise.

Since in-order traversal of a BST visits nodes in ascending order, the iterator should return values from smallest to largest. You may assume that next() is only called when hasNext() would return true.

Examples

Example 1

Input:

      10
     / \
    5   15
   / \    \
  3   7   18

["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "next", "next", "hasNext"]
[[root], [], [], [], [], [], [], [], [], []]

Output: [null, 3, 5, true, 7, true, 10, 15, 18, false]

Explanation:

  • BSTIterator(root) — Initializes the iterator with the BST. The in-order sequence is [3, 5, 7, 10, 15, 18].
  • next() → returns 3 (the smallest element).
  • next() → returns 5 (the second smallest).
  • hasNext() → returns true (four elements remain: 7, 10, 15, 18).
  • next() → returns 7.
  • hasNext() → returns true (three elements remain).
  • next() → returns 10.
  • next() → returns 15.
  • next() → returns 18 (the largest element).
  • hasNext() → returns false (all elements have been visited).

Example 2

Input:

    3
   /
  2
 /
1

["BSTIterator", "hasNext", "next", "next", "next", "hasNext"]
[[root], [], [], [], [], []]

Output: [null, true, 1, 2, 3, false]

Explanation:

  • BSTIterator(root) — Initializes the iterator with a left-skewed BST. The in-order sequence is [1, 2, 3].
  • hasNext() → returns true (three elements are available).
  • next() → returns 1.
  • next() → returns 2.
  • next() → returns 3.
  • hasNext() → returns false (all elements exhausted).

This left-skewed tree represents a worst-case scenario for tree height (h = n), which is relevant for space analysis.

Constraints

  • 1 ≤ Number of nodes in the tree ≤ 10^5
  • 0 ≤ Node.val ≤ 10^6
  • At most 10^5 calls will be made to hasNext and next
  • All calls to next() are valid (i.e., hasNext() would return true at the time of the call)

Follow-up: Can you implement next() and hasNext() to run in average O(1) time and use only O(h) memory, where h is the height of the tree?

Editorial

Brute Force

Intuition

The most natural way to iterate through a BST in sorted order is to first perform a full in-order traversal and collect all values into an array. Once we have this sorted list, the iterator becomes trivially simple: next() just reads the next element from the array, and hasNext() checks whether we have reached the end.

Think of it like a librarian who, before opening the library, walks through every shelf and writes down every book title in alphabetical order on a master list. When visitors ask for the next book, the librarian simply reads the next entry from the list — no need to walk back to the shelves.

This approach trades space for simplicity: we do all the heavy lifting upfront during initialization, making every subsequent operation instant.

Step-by-Step Explanation

Let's trace through the BST from Example 1:

      10
     / \
    5   15
   / \    \
  3   7   18

Step 1: Constructor is called. Perform a complete in-order traversal of the BST.

  • Visit left subtree of 10: go to 5, then its left subtree: go to 3.
  • 3 has no children, record 3. Back to 5, record 5. Visit right of 5: record 7.
  • Back to 10, record 10. Visit right subtree: go to 15, record 15. Visit right of 15: record 18.
  • Resulting sorted array: vals = [3, 5, 7, 10, 15, 18]. Set cursor = 0.

Step 2: next() is called.

  • Return vals[0] = 3. Advance cursor to 1.

Step 3: next() is called.

  • Return vals[1] = 5. Advance cursor to 2.

Step 4: hasNext() is called.

  • Is cursor (2) < length (6)? Yes. Return true. Four elements remain.

Step 5: next() is called.

  • Return vals[2] = 7. Advance cursor to 3.

Step 6: Three more next() calls return 10, 15, and 18 in order. Cursor reaches 6.

Step 7: hasNext() is called.

  • Is cursor (6) < length (6)? No. Return false. The iterator is exhausted.

Brute Force Iterator — Array-Based Traversal — Watch how the brute force approach flattens the BST into a sorted array during initialization, then simply advances a cursor for each next() call.

Algorithm

Constructor:

  1. Initialize an empty list vals and set cursor = 0.
  2. Perform a recursive in-order traversal of the BST, appending each node's value to vals.
  3. After traversal, vals contains all values in ascending order.

next():

  1. Read the value at vals[cursor].
  2. Increment cursor by 1.
  3. Return the value.

hasNext():

  1. Return true if cursor < vals.length, otherwise false.

Code

class BSTIterator {
    vector<int> vals;
    int cursor;

    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        vals.push_back(node->val);
        inorder(node->right);
    }

public:
    BSTIterator(TreeNode* root) : cursor(0) {
        inorder(root);
    }

    int next() {
        return vals[cursor++];
    }

    bool hasNext() {
        return cursor < (int)vals.size();
    }
};
class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.vals = []
        self.cursor = 0
        self._inorder(root)

    def _inorder(self, node):
        if not node:
            return
        self._inorder(node.left)
        self.vals.append(node.val)
        self._inorder(node.right)

    def next(self) -> int:
        val = self.vals[self.cursor]
        self.cursor += 1
        return val

    def hasNext(self) -> bool:
        return self.cursor < len(self.vals)
class BSTIterator {
    private List<Integer> vals;
    private int cursor;

    public BSTIterator(TreeNode root) {
        vals = new ArrayList<>();
        cursor = 0;
        inorder(root);
    }

    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        vals.add(node.val);
        inorder(node.right);
    }

    public int next() {
        return vals.get(cursor++);
    }

    public boolean hasNext() {
        return cursor < vals.size();
    }
}

Complexity Analysis

Time Complexity:

  • Constructor: O(n) — the in-order traversal visits every node once to build the sorted array.
  • next(): O(1) — a single array access and pointer increment.
  • hasNext(): O(1) — a single integer comparison.

Space Complexity: O(n)

The vals array stores all n node values. Additionally, the recursive in-order traversal uses O(h) space on the call stack (where h is tree height). Since the array dominates, overall space is O(n).

Why This Approach Is Not Efficient

While the brute force gives us O(1) per operation after initialization, it has a critical weakness: O(n) space consumption.

The entire BST is flattened into an array during the constructor, regardless of how many elements the caller actually needs. Imagine a BST with 100,000 nodes where the caller only wants the first 5 smallest values — we still store all 100,000 values upfront. This is wasteful.

The follow-up challenge specifically asks for O(h) memory, where h is the tree height. For a balanced BST with a million nodes, h ≈ 20 — compared to storing a million elements, that is a 50,000× reduction in memory.

The key insight is that we do not need to know every future value upfront. We only need to know the next value at any given time. If we can simulate the in-order traversal incrementally — producing one value at a time on demand — we only need to remember our current position in the traversal, which requires just O(h) space (the path from root to the current node).

Optimal Approach - Controlled Stack

Intuition

In a recursive in-order traversal, the call stack naturally keeps track of where we are in the tree. The problem is that a recursive traversal runs to completion — it cannot pause and resume. We need a way to control the traversal, producing one value at a time.

The solution is to use an explicit stack to simulate what the call stack does during recursion. The core idea has two parts:

Initialization: Push the root and all its left descendants onto the stack. The top of the stack is always the next smallest unvisited node.

next() operation: Pop the top node (this is the next value to return). If the popped node has a right child, push that right child and all of ITS left descendants onto the stack. This ensures the stack's top remains the next smallest unvisited node.

Think of it like reading a book with chapters and sub-chapters. You bookmark the current page (stack tracks the path). When you finish a section, you check if there is a sub-section to the right (right child). If so, you dive into its leftmost subsection. If not, you return to the parent bookmark.

The stack never holds more than h nodes at once (where h is the tree height), because it only stores the path from the root to the current position — giving us the O(h) space the follow-up requests.

Step-by-Step Explanation

Let's trace the stack-based iterator on Example 1's BST:

      10
     / \
    5   15
   / \    \
  3   7   18

Step 1: Constructor is called with root = 10.

  • Call pushAllLeft(10): push 10, then go left to 5, push 5, then go left to 3, push 3. Node 3 has no left child — stop.
  • Stack (bottom → top): [10, 5, 3].

Step 2: next() is called.

  • Pop 3 from the stack. Node 3 has no right child, so nothing new is pushed.
  • Stack: [10, 5]. Return 3.

Step 3: next() is called.

  • Pop 5 from the stack. Node 5 has right child 7.
  • Call pushAllLeft(7): push 7. Node 7 has no left child — done.
  • Stack: [10, 7]. Return 5.

Step 4: next() is called.

  • Pop 7 from the stack. Node 7 has no right child.
  • Stack: [10]. Return 7.

Step 5: next() is called.

  • Pop 10 from the stack. Node 10 has right child 15.
  • Call pushAllLeft(15): push 15. Node 15 has no left child — done.
  • Stack: [15]. Return 10.

Step 6: next() is called.

  • Pop 15 from the stack. Node 15 has right child 18.
  • Call pushAllLeft(18): push 18. Node 18 has no left child — done.
  • Stack: [18]. Return 15.

Step 7: next() is called.

  • Pop 18 from the stack. Node 18 has no right child.
  • Stack: []. Return 18.

Step 8: hasNext() is called.

  • Stack is empty. Return false. All elements have been visited in order: 3, 5, 7, 10, 15, 18.

Controlled Stack — Incremental In-Order Traversal — Watch how the stack simulates a paused in-order traversal. Each next() pops the current smallest, and if the popped node has a right child, pushes its left chain to maintain the invariant.

Algorithm

Helper — pushAllLeft(node):

  1. While node is not null: push node onto the stack, then move to node.left.

Constructor:

  1. Initialize an empty stack.
  2. Call pushAllLeft(root) to prepare the first element.

next():

  1. Pop the top node from the stack.
  2. If the popped node has a right child, call pushAllLeft(right child).
  3. Return the popped node's value.

hasNext():

  1. Return true if the stack is not empty, false otherwise.

Code

class BSTIterator {
    stack<TreeNode*> stk;

    void pushAllLeft(TreeNode* node) {
        while (node != nullptr) {
            stk.push(node);
            node = node->left;
        }
    }

public:
    BSTIterator(TreeNode* root) {
        pushAllLeft(root);
    }

    int next() {
        TreeNode* node = stk.top();
        stk.pop();
        if (node->right != nullptr) {
            pushAllLeft(node->right);
        }
        return node->val;
    }

    bool hasNext() {
        return !stk.empty();
    }
};
class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self._push_all_left(root)

    def _push_all_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self) -> int:
        node = self.stack.pop()
        if node.right:
            self._push_all_left(node.right)
        return node.val

    def hasNext(self) -> bool:
        return len(self.stack) > 0
class BSTIterator {
    private Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new ArrayDeque<>();
        pushAllLeft(root);
    }

    private void pushAllLeft(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }

    public int next() {
        TreeNode node = stack.pop();
        if (node.right != null) {
            pushAllLeft(node.right);
        }
        return node.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

Complexity Analysis

Time Complexity:

  • Constructor: O(h) — we push at most h nodes (the leftmost path) onto the stack.
  • next(): O(1) amortized — while a single next() call might push up to h nodes (when the popped node has a right subtree), each node in the entire tree is pushed and popped exactly once across all next() calls. Over n calls to next(), the total work is O(n), giving O(1) amortized per call.
  • hasNext(): O(1) — a single stack emptiness check.

Space Complexity: O(h), where h is the height of the tree

The stack stores at most the nodes along the path from the root to the current leftmost node. For a balanced BST, h = O(log n). For a completely skewed tree, h = O(n) in the worst case. This meets the follow-up requirement of O(h) memory, which is a significant improvement over the brute force O(n) for balanced trees.