Lowest Common Ancestor of a Binary Search Tree

Given the root of a binary search tree and two node values p and q (both guaranteed to exist, all values unique), return the value of their lowest common ancestor (LCA) — the deepest node that has both as descendants (a node is a descendant of itself).

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Use the BST ordering instead of the general tree-LCA recursion.

If both values are smaller than the node, go left; if both larger, go right.

The first node where they split (or one equals the node) is the LCA.

Common doubts

It's the deepest node that still has p on one side and q on the other (or is one of them), which is exactly the definition of the lowest common ancestor.

The ordering lets you descend one path in O(height) with O(1) space, instead of searching both subtrees.

Then that node is an ancestor of the other value and is the LCA — the 'split' branch handles it.

Interview follow-ups

· What an interviewer asks next.

Without ordering you recurse into both subtrees and return the node where the two finds meet (LeetCode 236).

Depth(p) + depth(q) - 2*depth(LCA), each found by a BST descent.

Fun facts

The LCA descent is the point where a search for p and a search for q would first diverge.
This is the cleanest example of a BST turning an O(n) tree problem into an O(height) walk.

Asked at

AmazonMicrosoftFacebook

Frequently Sometimes Occasionally

Example 1

Input: root = [6, 2, 8, 0, 4, 7, 9], p = 2, q = 8
Output: 6
2 is in the left subtree and 8 in the right, so they split at the root.

Example 2

Input: root = [6, 2, 8, 0, 4, 7, 9], p = 2, q = 4
Output: 2
4 is a descendant of 2, and a node is its own ancestor.

Constraints

- The number of nodes is in the range [2, 10^5] - -10^9 <= Node.val <= 10^9 - All Node.val are unique - p and q exist in the BST

On a BST you don't need the general tree-LCA recursion — the ordering does the work. Compare both values to the current node: if both are smaller, the LCA is in the left subtree; if both are larger, the right; otherwise the values split here (or one equals this node), so this node is the LCA. One walk down — O(height), O(1) space.

Prerequisites

Before you start

· Concepts used directly in the solution.

BST invariant. Left < node < right, everywhere.

Split point. The LCA is where p and q first go different ways.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Are p and q guaranteed present?”

Yes, and all values are unique.

“Is a node its own ancestor?”

Yes — if p is an ancestor of q, the LCA is p.

The ideal opening — say it like this

On a BST I compare both values to the node: both smaller means go left, both larger means go right.

The first node where they split — or where one equals the node — is the lowest common ancestor.

Understand the problem

Worked example — BST [6, 2, 8, 0, 4, 7, 9], p = 2, q = 8

6: 2 < 6 and 8 > 6 -> they split here -> LCA = 6

Key observations

1Aha

Both smaller / both larger picks the side

When p and q are on the same side, the LCA is deeper on that side.

2Aha

The split point is the LCA

The first node where they go different ways is their lowest common ancestor.

3Aha

O(height), O(1) space

It's a single descent, no stack or recursion needed.

Brute force vs optimal

	Recursive by comparison	Iterative by comparison
Idea	Recurse the side both values fall on	Loop down to the split point
Time	O(height)	O(height)
Space	O(height)	O(1)

Both use the ordering; the iterative version is O(1) space. Full code is in the Approaches selector below.

Summary

Key takeaway

Descend the BST: both values smaller ⇒ go left, both larger ⇒ go right, otherwise this node is the LCA. O(height) time, O(1) space.

while node:
    if p < node and q < node: node = node.left
    elif p > node and q > node: node = node.right
    else: return node