Lowest Common Ancestor of a BST
Lowest Common Ancestor of a BST is a medium Trees problem from the Blind 75. The key pattern is bst walk, and a good solution runs in O(h) time.
Problem
Given a BST and two values present in it, return the value of their lowest common ancestor.
Examples
Example 1
Input
{"tree":[8,3,10,1,6,null,14],"p":1,"q":6}Output
3Example 2
Input
{"tree":[20,10,30,5,15,25,35,null,null,12,18],"p":10,"q":30}Output
20Example 3
Input
{"tree":[20,10,30,5,15,25,35,null,null,12,18],"p":10,"q":15}Output
10Approach
From the root, go left while both values are smaller and right while both are larger. The first node that splits them, or equals one of them, is the answer.
| Pattern | BST walk |
|---|---|
| Time | O(h) |
| Space | O(1) |
Watch out for
A node is its own ancestor, so one value can be the answer itself.