Course contentsShow
← Computer Science
Lesson 518 of 2,87212. Binary Search TreesFree lesson

Lowest Common Ancestor in BST

Find the LCA by leveraging BST ordering to determine when two nodes diverge into different subtrees.

Lowest Common Ancestor in BST

You'll learn how to efficiently find the lowest common ancestor of two nodes by exploiting BST ordering.

The Core Idea

The Lowest Common Ancestor (LCA) of two nodes in a tree is the deepest node that has both nodes as descendants (where a node can be its own descendant). In a BST, finding the LCA is elegant because the BST property tells us exactly when two nodes "split apart" into different subtrees.

Here's the key insight: Starting from the root, if both target nodes are smaller than the current node, they must both be in the left subtree. If both are larger, they're both in the right subtree. But when one node is smaller and one is larger (or one equals the current node), you've found where their paths diverge—that's the LCA!

How It Works

Imagine you're looking for the LCA of nodes with values 3 and 7 in a BST:

  • Start at root (say, value 5)
  • Is 3 < 5? Yes. Is 7 < 5? No.
  • They're on opposite sides of 5, so 5 is the LCA

Compare this to finding the LCA of 3 and 4:

  • At root 5: both 3 and 4 are < 5, so go left
  • Continue until you find the split point where they diverge

The BST ordering eliminates the need to explore both subtrees—you know exactly which direction to go at each step, making this O(h) where h is tree height.

Key Takeaway: In a BST, the LCA is the first node where the two target values split into different subtrees, leveraging the BST property to guide the search efficiently without exploring unnecessary paths.