Lowest Common Ancestor 20 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

The Lowest Common Ancestor (LCA) of two nodes p and q in a BST is the deepest node that has both p and q as descendants (a node can be a descendant of itself).

#       6
#      / \
#     2   8
#    / \ / \
#   0  4 7  9
#     / \
#    3   5
# LCA(2, 8) = 6  (split point)
# LCA(2, 4) = 2  (2 is ancestor of 4)
# LCA(3, 5) = 4

In a BST, the LCA is the split point where p and q diverge to different subtrees:

If both p and q are smaller than current → LCA is in left subtree
If both p and q are larger than current → LCA is in right subtree
Otherwise → current node IS the LCA (they split here)

The BST property makes this O(h) instead of O(n) for a general binary tree. Elegant!

📋 Instructions

Implement `lowest_common_ancestor(root, p, q)` for a BST. Test with different pairs of nodes.

Start at root. If both p and q < root.val, go left. If both > root.val, go right. Otherwise, this is the split point — return root.val.

🧪 Test Cases

Input

lowest_common_ancestor(root, 2, 8)

Expected

6

Test case 1

Input

lowest_common_ancestor(root, 2, 4)

Expected

2

Test case 2

Input

lowest_common_ancestor(root, 3, 5)

Expected

4

Test case 3

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›