LeetCode · #235

Lowest Common Ancestor of a BST Solution

Given a BST, find the lowest common ancestor (LCA) of two given nodes.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #235

🏗️

Pattern

BST — split point detection

Given a BST and two nodes p and q, find their lowest common ancestor — the deepest node that has both p and q as descendants (a node is allowed to be a descendant of itself).

Example

 Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6 // 2 is in left subtree, 8 is in right → root 6 is the split point 

Constraints

 • 2 ≤ number of nodes ≤ 10⁵ • All values are unique • p ≠ q, both exist in the BST 

Section Two · Approach 1

Generic LCA (no BST property) — O(n)

Ignore the BST ordering and use the general binary tree LCA approach: recursively search both subtrees. Works but doesn't exploit the sorted property — always visits O(n) nodes.

Section Three · Approach 2

BST Split Point — O(H)

In a BST, the LCA is the first node where p and q split — one goes left, the other goes right (or one equals the current node). If both are smaller, go left. If both are larger, go right. Otherwise, the current node is the LCA.

💡 Mental model: Walk down from the root. At each fork, both friends need to go the same direction (both smaller → go left; both bigger → go right). The first time they need to split up — one goes left, the other right — you're standing at their meeting point.

Algorithm

If both p and q < node → go left.
If both p and q > node → go right.
Else → current node is the LCA (split point or one matches).

🎯 Why O(H), not O(n)? We only walk one root-to-node path. In a balanced BST, H = O(log n). In a skewed BST, H = O(n) worst case.

Section Four · Trace

Visual Walkthrough

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

Section Five · Implementation

Code — Java & Python

Java — Iterative

 class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (p.val < root.val && q.val < root.val) {
                root = root.left;
            } else if (p.val > root.val && q.val > root.val) {
                root = root.right;
            } else {
return root; // split point = LCA
}
        }
return null;
    }
}

Python — Iterative

 class Solution:
def lowestCommonAncestor(self, root, p, q):
while root:
if p.val < root.val and q.val < root.val:
                root = root.left
elif p.val > root.val and q.val > root.val:
                root = root.right
else:
return root

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Generic LCA	O(n)	O(n)
BST split ← optimal	O(H)	O(1)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
One is ancestor	p=2, q=4 (4 under 2)	At node 2: q=4 > 2 → split. LCA = 2 (p itself).
Adjacent nodes	p=3, q=4	Split happens at their parent.
Root is LCA	p = leftmost, q = rightmost	Root is always a common ancestor — but might be the lowest too.

⚠ Common Mistake: Forgetting that a node can be its own ancestor. If p = 2 and q = 4, and 4 is in 2's subtree, the LCA is 2 — not 2's parent. The "else" case correctly returns the current node when one value matches.

← Back to BST problems

LearningTree

LC 235 · Lowest Common Ancestor of a BST — Solution & Explanation | DSA Guide