Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
The first call to
next() will return the smallest number in BST. Calling
next() again will return the next smallest number in the BST, and so on.
hasNext()should run in average
O(1)time and uses
his the height of the tree.
Try to optimize the additional space complexity apart from the amortized time complexity.
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.