Practice/Meta/Leetcode 173. Binary Search Tree Iterator

Leetcode 173. Binary Search Tree Iterator

CodingMust

Problem

Design and implement an iterator class for a Binary Search Tree (BST) that allows sequential traversal of the tree's values in sorted (ascending) order. Your iterator should support two operations:

• next(): Returns the next smallest number in the BST
• hasNext(): Returns whether there are more elements to iterate over

The iterator should be initialized with the root node of a BST. When constructed, it should position itself before the first element, so that the first call to next() returns the smallest element in the tree.

Requirements

1. Implement the BSTIterator class with a constructor that takes the root of a BST
2. Implement next() to return the next smallest element in the tree
3. Implement hasNext() to return true if there are more elements, false otherwise
4. Your implementation should optimize for space efficiency while maintaining good time complexity
5. The iterator should traverse elements in in-order (sorted ascending) sequence

Constraints

• The number of nodes in the tree is in the range [1, 10^5]
• 0 <= Node.val <= 10^6
• At most 10^5 calls will be made to hasNext and next
• You may assume all calls to next() will be valid (when there are elements remaining)
• Target complexity: next() and hasNext() should run in average O(1) time with O(h) space, where h is the height of the tree

Examples

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(); // returns 3 bSTIterator.next(); // returns 7 bSTIterator.hasNext(); // returns true bSTIterator.next(); // returns 9 bSTIterator.hasNext(); // returns true bSTIterator.next(); // returns 15 bSTIterator.hasNext(); // returns true bSTIterator.next(); // returns 20 bSTIterator.hasNext(); // returns false `

Example 2:

` Input: ["BSTIterator", "next", "hasNext"] [[[1]], [], []]

Output: [null, 1, false]

Explanation: A single-node tree returns its value on first next(), then hasNext() is false. `