Successor and Predecessor
The next value up is the last node you turned left at, or the minimum of the right subtree.
BST Queries: Successor from an ancestor
50 beats 40, so it is a candidate. Go left to look for something smaller that still beats 40.
Cost
- Best
- O(1)
- Average
- O(log n)
- Worst
- O(n)
- Space
- O(1)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
BST Queries covers these too, in the same run.