BST Range Search
Report every value in a range, entering only the subtrees that could hold one.
Decision · step 2 of 9BST Queries: Values between 35 and 65
50 is in range, so report it. Both sides could hold more, so look at both.
What you will see
Subtrees fully outside the range fade; in-range nodes are stamped in order.
Cost
| Best | O(log n) |
|---|---|
| Average | O(log n + k) |
| Worst | O(n) |
| Space | O(h) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Nodes announce value, left child and right child; each step announces the comparison and the direction taken or the structural change.
Reduced motion: Focus jumps node to node with a static ring; rotations become a crossfade between the two layouts.
Before this
Taught by the same lesson
BST Queries covers these too, in the same run.