{x}
blog image

Binary Search Tree Iterator

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.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

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 1:

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

 

Constraints:

  • The number of nodes in the tree is in the range [1, 105].
  • 0 <= Node.val <= 106
  • At most 105 calls will be made to hasNext, and next.

 

Follow up:

  • Could you implement next() and hasNext() to run in average O(1) time and use O(h) memory, where h is the height of the tree?

Solution Explanation and Code:

This problem requires implementing an iterator for an in-order traversal of a Binary Search Tree (BST). Two approaches are presented below: one using a pre-order traversal to store all nodes' values in an array, and another using a stack for iterative in-order traversal.

Approach 1: In-order Traversal and Storage

This approach performs a standard in-order traversal of the BST to collect all node values into an array (vals). The next() method then simply returns the next element from this array, and hasNext() checks if there are more elements remaining.

Time Complexity: O(N) for initialization (__init__ or constructor) where N is the number of nodes in the BST, due to the in-order traversal. next() and hasNext() are O(1).

Space Complexity: O(N) to store the vals array.

Code: (Python3, Java, C++, Go, TypeScript, Rust, Javascript examples provided in the original response)

Approach 2: Iterative In-order Traversal using Stack

This is a more efficient approach in terms of space complexity, especially for large and skewed trees. It uses a stack to simulate the recursive calls of an in-order traversal. The next() method pops the top element from the stack, which represents the next node in the in-order traversal. Then, it pushes the left children of the right subtree onto the stack. hasNext() simply checks if the stack is empty.

Time Complexity: O(1) on average for next() and hasNext(). The initialization (__init__ or constructor) is O(H) where H is the height of the tree in the worst case (skewed tree). In a balanced BST, H is log(N).

Space Complexity: O(H) where H is the height of the tree, due to the stack. This is significantly better than the first approach for tall trees.

Code: (Python3, Java, C++, TypeScript, Rust examples provided in the original response). Note that the Javascript example provided in the original response also uses a stack based approach.

Choosing the Right Approach:

  • If memory usage is not a significant concern and the tree is relatively small, Approach 1 (pre-order traversal and storage) is simpler to implement.
  • If dealing with a potentially very large or skewed BST, Approach 2 (iterative in-order traversal with a stack) is highly recommended due to its better space efficiency. It achieves the desired average O(1) time complexity for next() and hasNext().