LeetCode 173: Binary Search Tree Iterator Solution

Master LeetCode problem 173 (Binary Search Tree Iterator), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

173. Binary Search Tree Iterator

Medium

Stack Tree Design Binary Search Tree Binary Tree Iterator

Problem Explanation

Explanation

To implement the BSTIterator class, we can leverage the fact that an inorder traversal of a binary search tree gives the elements in sorted order. We can simulate the inorder traversal using a stack to keep track of the nodes as we traverse the tree. The constructor initializes the stack with all left children of the root. The next() function returns the next smallest element in the BST by popping from the stack and pushing the right children of the popped node. The hasNext() function returns true if the stack is not empty.

Time Complexity

Constructor: O(h) average case
hasNext(): O(1)
next(): Amortized O(1)

Space Complexity

O(h) where h is the height of the tree.

Solution Code

class BSTIterator {
    Stack<TreeNode> stack;

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

    public int next() {
        TreeNode node = stack.pop();
        pushLeftChildren(node.right);
        return node.val;
    }

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

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 173 (Binary Search Tree Iterator)?

This page provides optimized solutions for LeetCode problem 173 (Binary Search Tree Iterator) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 173 (Binary Search Tree Iterator)?

The time complexity for LeetCode 173 (Binary Search Tree Iterator) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 173 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 173 in Java, C++, or Python.

Back to LeetCode Solutions