927. BST Iterator (In-Order Lazy Evaluation)

Design an iterator over a binary search tree that returns keys in ascending order. Simulate repeatedly calling next() until hasNext() is false, and return the full sequence of keys produced, as an array. The tree is given as a level-order BST array.

Input: A level-order BST array.

Output: Array — the keys in ascending order.

Examples

Input: [7,3,15,null,null,9,20]
Output: [3,7,9,15,20]
Explanation: Inorder sequence from the iterator.

Input: [5]
Output: [5]
Explanation: Single key.

Input: []
Output: []
Explanation: Empty tree.

Constraints

• 0<=nodes<=10^4
• valid BST

Asked by