Lowest Common Ancestor in a BST

Difficulty: Hard · Topic: Trees

Build a BST from values, then return the value of the lowest common ancestor (LCA) of a and b (both guaranteed present). Use the BST property: the LCA is the first node where a and b stop going the same direction.

Examples

lca_bst([6,2,8,0,4,7,9,3,5], 2, 8)
→ 6

2 goes left, 8 goes right → split at the root.

lca_bst([6,2,8,0,4,7,9,3,5], 2, 4)
→ 2

4 is in 2's right subtree, so 2 is the ancestor.

lca_bst([6,2,8,0,4,7,9,3,5], 3, 5)
→ 4

Target complexity: time O(h), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.