Step Through a Search Tree One Value at a Time
Implement runIterator
An iterator over a binary search tree hands out the tree's values one at a time in ascending order. It supports next(), which returns the next smallest value not yet returned, and hasNext(), which tells whether any value is left. Here you are given the tree and a list of calls (1 = next, 0 = hasNext) and must return the answer to each call (a hasNext answer is 1 for true and 0 for false).
Copying the whole tree into a list is easy but uses memory proportional to the number of nodes. A stack that keeps only the pending path uses memory proportional to the height, and each node is still handled only once.
Example 1:
Input: root = [300,200,400,150,250,350,450], ops = [1,1,0,1]
Output: [150,200,1,250]
Example 2:
Input: root = [300], ops = [0,1,0]
Output: [1,300,0]
Example 3:
Input: root = [], ops = [0]
Output: [0]
+ 12 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100; all node values are distinct, 100 ≤ node.val ≤ 999 (so a value can never be confused with a 0 or 1 answer) - ●
The tree is a binary search tree (left subtree smaller, right subtree larger), given by its root node - ●
ops lists calls made on an iterator over the tree's values in ascending order: 1 means next() — return the next smallest value that has not been returned yet; 0 means hasNext() — return 1 if such a value exists, otherwise 0. 0 ≤ ops.length ≤ 60, and next() is never requested when nothing is left - ●
Return the answers to the calls, in order. The iterator should not have to store all the values: an approach using memory proportional to the tree height h is the target
root =
ops =