algoadvance

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

• 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. That is, there will be at least a next number in the in-order traversal when next() is called.

Example:

Input:
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]

Output:
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation: BSTIterator bstIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); bstIterator.next(); // return 3 bstIterator.next(); // return 7 bstIterator.hasNext(); // return True bstIterator.next(); // return 9 bstIterator.hasNext(); // return True bstIterator.next(); // return 15 bstIterator.hasNext(); // return True bstIterator.next(); // return 20 bstIterator.hasNext(); // return False

Clarifying Questions

1. What is the structure of the TreeNode class?
2. Are there any constraints on the values within the tree nodes?
3. Should the class handle the possibility of an empty tree?

Strategy

To solve this problem, we’ll use a stack-based approach to simulate the controlled traversal of the BST in an iterative manner:

1. Initialization (__init__):
   • We will initiate the BST traversal by pushing all left children of the root to the stack until we reach the leftmost node.
2. hasNext Method:
   • Check if there are any elements left in the stack.
3. next Method:
   • Pop the top element from the stack.
   • For the popped node, push all of its right children’s left descendants onto the stack.
   • Return the value of the popped node.

Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BSTIterator:
    def __init__(self, root: TreeNode):
        self.stack = []
        self._leftmost_inorder(root)
    
    def _leftmost_inorder(self, root):
        while root:
            self.stack.append(root)
            root = root.left
    
    def next(self) -> int:
        topmost_node = self.stack.pop()
        if topmost_node.right:
            self._leftmost_inorder(topmost_node.right)
        return topmost_node.val
    
    def hasNext(self) -> bool:
        return len(self.stack) > 0

# Example usage:
# Construct the tree:
#      7
#     / \
#    3  15
#       / \
#      9  20

root = TreeNode(7)
root.left = TreeNode(3)
root.right = TreeNode(15)
root.right.left = TreeNode(9)
root.right.right = TreeNode(20)

# Create the iterator
iterator = BSTIterator(root)

print(iterator.next())    # return 3
print(iterator.next())    # return 7
print(iterator.hasNext()) # return True
print(iterator.next())    # return 9
print(iterator.hasNext()) # return True
print(iterator.next())    # return 15
print(iterator.hasNext()) # return True
print(iterator.next())    # return 20
print(iterator.hasNext()) # return False

Time Complexity

• The average time complexity for the next and hasNext operations is O(1), although in the worst case, next can be O(h) where h is the height of the tree. This is because each node is pushed and popped from the stack exactly once.
• The space complexity of the BSTIterator is O(h) where h refers to the height of the tree, since the stack holds at most all the nodes along a path from the root to the deepest leaf.

Try our interview co-pilot at AlgoAdvance.com

• 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?