← Back to problems Solve on LeetCode → See #700 Search BST →

Lowest Common Ancestor of BST

LeetCode 235 • Easy • Trees

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 → Output: 6
LCA: first node where p and q diverge. If both < root go left, both > root go right, else root is LCA.

TimeO(h)path height

SpaceO(1)pointer only

Current: —

Current

LCA / Path

p, q

Current

—

Speed:

Ready

Press Play. While both p,q on same side of root: root = root.left or root.right. Else root is LCA.

✎ Whiteboard

Size:3

⌨ Type It — Iterative

Practice until you don't need to look. The green highlights are the nuances to burn into memory.

═══ LCA of BST — ITERATIVE ═══

PATTERN ▸ BST property (both left or both right) O(h) · O(1)

① LOOP

while root:

② BRANCH

if p.val < root.val and q.val < root.val: root = root.left

elif p.val > root.val and q.val > root.val: root = root.right

else: return root

▼ your implementation ▼

Verify your solution:

⌨ Type It — Recursive

Practice until you don't need to look. If both < root recurse left, both > root recurse right, else return root.

═══ LCA of BST — RECURSIVE ═══

PATTERN ▸ BST property O(h) · O(h)

① BOTH LEFT

if p.val < root.val and q.val < root.val: return lowestCommonAncestor(root.left, p, q)

② BOTH RIGHT

if p.val > root.val and q.val > root.val: return lowestCommonAncestor(root.right, p, q)

③ SPLIT OR FOUND

return root

▼ your implementation ▼

Verify your solution: