Successor and Predecessor
The next value up is the last node you turned left at, or the minimum of the right subtree.
Decision · step 2 of 5BST Queries: Successor from an ancestor
50 beats 40, so it is a candidate. Go left to look for something smaller that still beats 40.
What you will see
Focus goes right once then left as far as possible, or climbs until it comes from a left child.
Cost
| Best | O(1) |
|---|---|
| Average | O(log n) |
| Worst | O(n) |
| Space | O(1) |
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
Related
Taught by the same lesson
BST Queries covers these too, in the same run.