Loading problem…
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.
Example 1
Input: operations = ["BSTIterator","next","next","hasNext","next","hasNext","next","hasNext","next","hasNext"], arguments = [[[7,3,15,null,null,9,20]],[],[],[],[],[],[],[],[],[]]
Output: [null,3,7,true,9,true,15,true,20,false]
Explanation: The in-order traversal of the tree is 3, 7, 9, 15, 20. Each next() returns the following value in that order, and hasNext() is true until 20 has been returned, after which it is false.
Example 2
Input: operations = ["BSTIterator","hasNext","next","hasNext","next","hasNext"], arguments = [[[1,null,2]],[],[],[],[],[]]
Output: [null,true,1,true,2,false]
Explanation: The tree is 1 with a right child 2, so the in-order order is 1, 2. hasNext() is true before each next() and false after 2 has been returned.
Example 3
Input: operations = ["BSTIterator","next","next","next","next"], arguments = [[[5,3,7,2,4,6,8]],[],[],[],[]]
Output: [null,2,3,4,5]
Explanation: The in-order traversal of this tree is 2, 3, 4, 5, 6, 7, 8. Four calls to next() return the four smallest values: 2, 3, 4, 5.
A recursive in-order traversal visits nodes in sorted order, but we can't pause a recursion between calls. So we make the recursion explicit with a stack: the stack always holds the chain of ancestors whose values still need to be returned. Its top is always the next value in sorted order, so next() is a pop plus a small fix-up, and hasNext() is just 'is the stack non-empty?'.
Run checks all cases above. Submit evaluates all test cases.