Binary Search Tree Iterator – 173. LeetCode

The Binary Search Tree (BST) Iterator problem asks you to implement an iterator for a BST. This iterator must support operations to efficiently traverse the BST in inorder (left → root → right) order. The iterator needs to provide the next smallest element in the BST using the next() method and must check if there are more elements using the hasNext() method. This problem tests your understanding of tree traversal, efficient data structure usage, and the iterator pattern.

Brute Force Approach

The brute force approach involves:

1. Flattening the BST into a sorted list during initialization by performing an inorder traversal.

2. Using the list to implement next() and hasNext().

import java.util.*;

public class BSTIterator {
    private List<Integer> nodesSorted;
    private int index;

    public BSTIterator(TreeNode root) {
        nodesSorted = new ArrayList<>();
        index = -1;
        inorderTraversal(root, nodesSorted);
    }

    private void inorderTraversal(TreeNode node, List<Integer> result) {
        if (node == null) return;
        inorderTraversal(node.left, result);
        result.add(node.val);
        inorderTraversal(node.right, result);
    }

    public int next() {
        return nodesSorted.get(++index);
    }

    public boolean hasNext() {
        return index + 1 < nodesSorted.size();
    }
}

• Perform a full inorder traversal of the BST and store the elements in a list.

• This ensures all elements are sorted in ascending order.

• next() retrieves the next element from the list using an index.

• hasNext() checks if there are more elements left.

Optimized Approach: Stack-Based Traversal

The optimized approach avoids storing all elements of the BST upfront. Instead, it uses a stack to simulate the recursive traversal and process elements on demand. This significantly reduces space usage and defers computation until needed.

• Algorithm: Iterative Inorder Traversal.

• Data Structure: A stack to keep track of the current path in the tree.

public class BSTIterator {
    private Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        pushLeft(root);
    }

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

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

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

Step 1: Initialize stack

public BSTIterator(TreeNode root) {
    stack = new Stack<>();
    pushLeft(root);
}

• Ensures the iterator is set up with the smallest node (first in inorder sequence) at the top of the stack.

• The pushLeft() method prepares the iterator to start from the leftmost path, which is the first node in the inorder traversal.

Step 2: pushLeft() method

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

• Ensures that the stack contains nodes in the order they need to be visited.

• Maintains the invariant that the top of the stack is always the next node to visit in inorder traversal.

Step 3: next() method

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

• Implements the iterator’s next() function, which returns the next value in the inorder sequence.

• Handles the right subtree of the popped node by pushing its leftmost path onto the stack.

Step 4: hasNext() method

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

• Returns true if the stack is not empty, indicating that there are more nodes to visit.

• Returns false if the stack is empty, meaning the traversal is complete.

Why This Code Works

• Initialization: Prepares the stack for inorder traversal by pushing leftmost nodes.

• next(): Pops the next smallest node and processes its right subtree.

• hasNext(): Checks if the stack contains more nodes.

This solution is efficient, space-saving, and adheres to best practices, ensuring optimal performance for large trees.