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.

Implement the BSTIterator class:

• BSTIterator(TreeNode root) initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
• boolean hasNext() returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
• int next() moves the pointer to the right, then returns the number at the pointer.

You may assume that next() calls will always be valid. i.e., there will be a next number in the BST when next() is called.

Clarifying Questions

1. What is the structure of the TreeNode class?
   • The TreeNode class is typically defined as:

     struct TreeNode {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode() : val(0), left(nullptr), right(nullptr) {}
         TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
         TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     };
     

2. What type of traversal should be used for the iterator?
   • The iterator should perform an in-order traversal to retrieve the elements in ascending order.
3. Is the BST mutable during the iteration process?
   • For the scope of this problem, we’ll assume the BST is not modified during iteration.

Strategy

1. In-order Traversal using Stack:
   • Since we need the smallest element each time next() is called and BST properties ensure that the leftmost element is the smallest, we can use a stack to keep track of the nodes.
   • We will push all the left nodes to the stack initially. Whenever next() is called, the top of the stack will have the next smallest element.
2. Initialization:
   • During initialization, push all the left children of the root to the stack.
3. hasNext() and next():
   • hasNext() checks if the stack is not empty.
   • next() pops the top of the stack and processes the right subtree of the popped node.

Code

class BSTIterator {
public:
    BSTIterator(TreeNode* root) {
        pushAllLeft(root);
    }
    
    int next() {
        TreeNode* topNode = st.top();
        st.pop();
        pushAllLeft(topNode->right);
        return topNode->val;
    }
    
    bool hasNext() {
        return !st.empty();
    }

private:
    stack<TreeNode*> st;
    
    void pushAllLeft(TreeNode* node) {
        while (node != nullptr) {
            st.push(node);
            node = node->left;
        }
    }
};

// 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) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

Time Complexity

• Initialization (BSTIterator constructor):
  • The time complexity is O(h), where h is the height of the tree, as we traverse from the root down to the leftmost node.
• next() method:
  • Each call to next() has an average time complexity of O(1). Although, in the worst case (when the node has a non-null right child), it can be O(h).
• hasNext() method:
  • The time complexity is O(1) as it simply checks if the stack is empty or not.

In summary, the BSTIterator class efficiently traverses the BST in in-order fashion, maintaining O(h) space complexity for the stack and average O(1) complexity for operations.

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?