AlgoScope

Successor and Predecessor

The next value up is the last node you turned left at, or the minimum of the right subtree.

Tree algorithms, algorithm, intermediate
At 50. It beats 40, so it is remembered and the walk turns left.2030354050607080current50 > 40
At 50. It beats 40, so it is remembered and the walk turns left.2030354050607080current50 > 40

BST Queries: Successor from an ancestor

Decision, step 2 of 5

50 beats 40, so it is a candidate. Go left to look for something smaller that still beats 40.

How bst queries works

Cost

Best
O(1)
Average
O(log n)
Worst
O(n)
Space
O(1)

Leads to

Topics that need this one first.

Taught by the same lesson

BST Queries covers these too, in the same run.