Skip to content
Onsite
20 / 29

Binary Search Tree Iterator

MediumP3Coding

Implement an iterator over the in-order traversal of a binary search tree.

  • BSTIterator(root) creates the iterator from the root of the BST. The pointer starts before the smallest value.
  • next() moves the pointer right and returns the value it now points to.
  • hasNext() returns true if there is a value to the right of the pointer.

next() is only called when hasNext() is true. Aim for O(1) amortised time per call and O(h) memory, where h is the tree height.

Example 1

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]

Constraints

  • 1 <= number of nodes <= 10^5
  • 0 <= Node.val <= 10^6
  • At most 10^5 calls to next and hasNext.

Hints

Run checks the 2 visible tests, Submit all 6.