BST Iterator

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.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
Try to optimize the additional space complexity apart from the amortized time complexity.

Interview Code Editor
Hints
  • Solution Approach
  • Complete Solution
3185 successful submissions.
Asked In:
  • Apple
  • Amazon
  • Facebook
Click here to jump start your coding interview preparation