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.