O41

Binary Search Tree Iterator

Mid / Senior Engineer
Target Time: 25 - 35 Minutes
Type: ARRAY

Problem Statement & Objective

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree with O(1) average time and O(h) memory.

Function Signature (Python)

binary_search_tree_iterator(root: list, operations: list[str]) -> list

Input & Output Contract

Output Rule:Sorgu sonuçları listesi (sayı veya boolean).

System Constraints

1 <= agac.length <= 10^4
İşlemler: 'next' ve 'hasNext'
next() çağrıları her zaman geçerli bir eleman varken yapılır

Example Execution Walkthrough

agac = [7, 3, 15, None, None, 9, 20]
islemler = ['next', 'next', 'hasNext', 'next', 'hasNext']
cevap: [3, 7, True, 9, True]

Example Test Scenarios (3)

Example 1
Input:[[7,3,15,null,null,9,20],["next","next","hasNext","next","hasNext"]]
Expected Output:[3,7,true,9,true]
Example 2
Input:[[5],["hasNext","next","hasNext"]]
Expected Output:[true,5,false]
Example 3
Input:[[3,1,4],["next","next","next","hasNext"]]
Expected Output:[1,3,4,false]
Loading Python Editor...
Input Parameters
[
  [
    7,
    3,
    15,
    null,
    null,
    9,
    20
  ],
  [
    "next",
    "next",
    "hasNext",
    "next",
    "hasNext"
  ]
]
Expected Output
[
  3,
  7,
  true,
  9,
  true
]