516. Ordered Iterator

MediumBinary Search TreeStackDesignIterator3 hints
RPby Rohit Parihar

A ledger keeps entries in a binary search tree, and a clerk wants to read them aloud from the smallest key to the largest, one entry at a time, without first copying the whole tree into a list.

Implement a class OrderedIterator. Its constructor receives the root of the search tree. next() returns the smallest key that has not been returned yet. hasNext() returns true if at least one key is still unreturned and false otherwise. next() is only called when keys remain. Every call should run in amortized O(1) time using O(h) memory, where h is the tree height. The tree may be empty.

Example 1

Input:
operations = ["OrderedIterator","next","next","hasNext","next","next","next","next","next","hasNext"]arguments = [[[12,5,18,2,9,15,21]],[],[],[],[],[],[],[],[],[]]
Output:
[null,2,5,true,9,12,15,18,21,false]
Explanation:

The keys come out in increasing order 2, 5, 9, 12, 15, 18, 21; hasNext is true while keys remain and false after 21 has been returned.

Example 2

Input:
operations = ["OrderedIterator","hasNext","next","hasNext"]arguments = [[[4]],[],[],[]]
Output:
[null,true,4,false]
Explanation:

A single node yields its key once and then hasNext becomes false.

Constraints

0 ≤ number of nodes ≤ 105

-104 ≤ node key ≤ 104

The tree is a valid binary search tree with distinct keys. At most 2 * 105 calls are made, and next() is called only while hasNext() would be true.

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.
Time per case
Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms

Expected complexity

Time
O(1) amortized per call
Space
O(h)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.