AlgoScope

Lowest Common Ancestor

Walk down while both values are on the same side. Where they split is the answer.

Tree algorithms, algorithm, intermediateAlso called LCA
At 50. Both values are on the same side.2030354050607080current
At 50. Both values are on the same side.2030354050607080current

BST Queries: Lowest common ancestor

Decision, step 2 of 4

Both 20 and 40 are smaller than 50, so both live to the left. Go left.

How bst queries works

Cost

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

Taught by the same lesson

BST Queries covers these too, in the same run.