AlgoScope

BST Range Search

Report every value in a range, entering only the subtrees that could hold one.

Tree algorithms, algorithm, intermediate
At 50. It is in range.203035405060657080current

BST Queries: Values between 35 and 65

Decision, step 2 of 9

50 is in range, so report it. Both sides could hold more, so look at both.

How bst queries works

Cost

Best
O(log n)
Average
O(log n + k)
Worst
O(n)
Space
O(h)

Taught by the same lesson

BST Queries covers these too, in the same run.