algoadvance

Leetcode 173. 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.

Example:

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return the next smallest number
iterator.hasNext(); // return whether we have a next smallest number

Note:

• next() and hasNext() should run in average O(1) time and use O(h) memory, where h is the height of the tree.
• You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

Clarifying Questions

1. What kind of values can the BST nodes contain?
   • The nodes contain integer values.
2. Can the BST contain duplicate values?
   • For the sake of this problem, let’s assume that the BST does not contain duplicate values.
3. Do we need to handle the initialization of the BST itself?
   • No, we only need to handle the iteration over an already constructed BST.

Strategy

We will use a stack to perform an in-order traversal of the tree, which will allow us to access the next smallest element in O(1) average time.

Here are the key points of our approach:

1. Initialization (BSTIterator(TreeNode root)):
   • We initialize a stack and push the leftmost path of the tree starting from the given root.
2. Next Element (next()):
   • The next() method pops the top element from the stack (which represents the current smallest unvisited element).
   • If the popped element has a right child, we push the leftmost path of that right subtree to the stack.
   • Return the value of the popped element.
3. Check for Next Element (hasNext()):
   • This method simply checks if there are any elements left in the stack.

Code

import java.util.Stack;

public class BSTIterator {
    private Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        // Initialize the stack with the leftmost path of the tree
        pushLeftPath(root);
    }
    
    /** @return the next smallest number */
    public int next() {
        TreeNode node = stack.pop();
        // If the node has a right child, push the leftmost path of the right subtree
        if (node.right != null) {
            pushLeftPath(node.right);
        }
        return node.val;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    // Helper function to push the leftmost path of a subtree onto the stack
    private void pushLeftPath(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

Time Complexity

• Initialization (BSTIterator(TreeNode root)): The initialization time is O(h) where h is the height of the BST, as we push the leftmost path onto the stack.

• Next Element (next()): Each call to next() runs in average O(1) time. This is because each node is pushed and popped from the stack exactly once.

• Check for Next Element (hasNext()): The hasNext() method runs in O(1) time because it simply checks if the stack is empty or not.

• Space Complexity: The space complexity is O(h) where h is the height of the BST, due to the stack storing nodes during traversal.

This approach ensures that we meet the problem’s constraints and efficiently iterate over the BST.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?