235. Lowest Common Ancestor of a BST

235

MediumTrees and Binary Search TreesBST property (value comparison)Walk down using BST ordering

Lowest Common Ancestor of a BST

Given a binary search tree and two nodes p and q that exist in it, return their lowest common ancestor: the deepest node that has both p and q as descendants (a node can be a descendant of itself).

Open official problem prompt ↗

In plain English

Locate the deepest node whose value sits between (or equals) the two target values, using only comparisons.

Picture it like this

Two people descend a family tree of sorted account numbers; they walk together as long as both belong on the same side, and part ways at the ancestor that splits them.

Example

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Why: 2 lies in the left subtree of 6 and 8 lies in its right subtree, so 6 is the deepest node covering both.

Constraints

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

Pattern lesson

See the pattern, then code

Walk down using BST ordering

↗

Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. The LCA is the first node where p and q fall on different sides (or one equals the node). While both values are smaller go left, while both are larger go right; the split point is the answer.

New words, made simpleKnow these before the algorithm

Lowest common ancestor: The deepest node that is an ancestor of both target nodes.
BST ordering: Left subtree values < node value < right subtree values.
Split point: The first node where the two targets diverge into different subtrees.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

General-tree LCA recursion

Correct but wastes the sorted structure and can visit the whole tree.

Recurse into both children and combine, ignoring the ordering.

Time O(n)Space O(h)

Best choiceOrdered downward walk

Follows one root-to-LCA path with constant memory.

Compare both values to the current node to pick a single direction until they split.

Time O(h)Space O(1)

The rule we keep true

Invariant

At every step the current node's subtree still contains both p and q.

Why this is correct

Reasoning

As long as both targets are on the same side, the ancestor cannot be the current node, so descend. The first node where they differ (or that equals a target) is the shallowest node still covering both from below, which is exactly the lowest common ancestor.

The algorithm in three movesSay these aloud before coding

1Start at the root

at 6: p=2<6, q=8>6 -> split

2If both p and q are less than the node, move left

return 6

3If both are greater, move right

4Otherwise the node is the split point; return it

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readnode 6

2 · AskSame side?

3 · Update statep.val=2<6, q.val=8>6

4 · Resulttargets split -> return 6

Key takeaway

At node 6 the targets 2 and 8 diverge left and right, marking the LCA.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Pointer at root
A single moving pointer avoids recursion and extra memory.
2
Lines 5-8Choose a side
If both values are smaller go left, if both larger go right; only one branch can hold both targets.
3
Lines 9-10Detect the split
When the values straddle the node (or one equals it), this node is the LCA.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

One of p or q is an ancestor of the other; the ancestor node itself is returned when the walk reaches it
p and q are direct children of the root
Minimum tree of two nodes

Common beginner mistakes

Using > and < without handling equality, which skips the case where a target equals the current node
Applying the generic O(n) tree LCA and losing the BST speedup
Comparing node identities instead of values when the BST guarantees unique values

Check your understanding

Why is comparing only values safe here even though the generic LCA compares node identity?

Lowest Common Ancestor of a BST

Lowest Common Ancestor of a BST

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trees and Binary Search Trees