149. Binary Search Tree Iterator
Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST): BSTIterator(root) initializes an object; the pointer starts before the smallest element. hasNext() returns true if there is a next number in the in-order traversal. next() moves the pointer right and returns the number at the pointer. Calls to next() are always valid: there is a next number when next() is called. next() and hasNext() should run in average O(1) time and use O(h) memory, where h is the height of the tree.
Examples
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: In-order traversal of the BST yields 3,7,9,15,20.
Constraints
- The number of nodes in the tree is between 1 and 10^5; 0 <= Node.val <= 10^6; at most 10^5 calls will be made to hasNext and next
Run checks all cases above. Submit evaluates all test cases.