Standard Bar Binary Search Trees · Practice Problems O(1) amortized per operation · O(h)
An audit terminal must stream a sorted archive one record at a time without ever loading it all into memory. The dispenser keeps only the leftmost unvisited spine of the filing tree on a small stack: each 'next' pops the smallest pending record and quietly loads that record's right wing's spine for later. 'hasNext' just peeks whether any spine remains.
Input: A binary search tree as a level-order array (null marks a missing child) and a list of calls, each 'next' or 'hasNext'. The first call sequence starts after initialization.
Output: Return the list of results for the calls in order — an integer for each 'next' and a boolean for each 'hasNext'.
1 <= number of nodes <= 10^5-10^9 <= node value <= 10^9next() and hasNext() run in amortized O(1); the stack may hold O(h) nodesAll calls are legal: next() is never called when hasNext() is falseInput: {"tree":[7,3,15,null,null,9,20],"calls":["next","next","hasNext","next","hasNext","next","next","hasNext"]}
Output: [3,7,true,9,true,15,20,false]
The dispenser streams the inorder sequence 3, 7, 9, 15, 20 and then runs dry.
Input: {"tree":[1],"calls":["next","hasNext"]}
Output: [1,false]
A one-node archive yields its single record and immediately reports exhaustion.