Lowest Common Ancestor of a Binary Search Tree (LC 235)

Pattern: BST Property Walk
Difficulty: Medium
Key Concept: Walk from the root: if both p and q are smaller than current, go left; if both larger, go right; otherwise current is the split → LCA.

Problem Statement

Given a BST root and two nodes p and q, return their lowest common ancestor (LCA).

The LCA is the lowest node that has p and q as descendants (a node can be a descendant of itself).

Input: BST, p, q (all values unique).
Output: TreeNode — LCA.

Example

        6
       / \
      2   8
     / \ / \
    0  4 7  9
      / \
     3   5

p = 2, q = 8 → LCA 6.
p = 2, q = 4 → LCA 2.

---

1. Algorithm & Pseudocode

Brute force

1. Find path from root to p and path to q (lists), then scan from the root for the last common node — O(h) time but O(h) extra space for two lists.

Pseudocode

pathP = pathFromRoot(root, p)
pathQ = pathFromRoot(root, q)
i = 0
while i < len(pathP) && i < len(pathQ) && pathP[i] == pathQ[i]:
    i++
return pathP[i-1]

Optimal

1. Start at cur = root.
2. While true:
   • If p.val < cur.val and q.val < cur.val → cur = cur.left.
   • Else if p.val > cur.val and q.val > cur.val → cur = cur.right.
   • Else cur is LCA (split, or one equals cur).

Pseudocode

cur = root
while true:
    if p.val < cur.val && q.val < cur.val: cur = cur.left
    else if p.val > cur.val && q.val > cur.val: cur = cur.right
    else: return cur

---

2. Step-by-Step Analysis (Beginner-Friendly)

• BST ordering lets you decide without searching entire subtrees: both smaller means both lie in left subtree, so LCA must be left too.
• Split means one node is in left subtree and the other in right (or one is the current node) — the current node is the deepest shared ancestor on the search path from root.
• Paths brute is correct but stores redundant data; the walk is implicit path comparison.

---

3. The Dry Run

Tree

        6
       / \
      2   8
     / \ / \
    0  4 7  9
      / \
     3   5

Case A: p=2, q=4

cur	Compare	Move
6	2<6, 4<6	left → 2
2	2==2 (split condition: one equals cur)	stop, LCA=2

ASCII (paths from root)

Root path to 2: 6 → 2
Root path to 4: 6 → 2 → 4
Common prefix ends at: 2

Case B: p=2, q=8

cur	Compare	Move
6	2<6, 8>6	split → LCA=6

        [6]   ← split: one left, one right
       /   \
      2     8

---

4. Java Solution

Brute Force

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

class SolutionBrute {
    // Time: O(h), Space: O(h) for paths
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = new ArrayList<>();
        List<TreeNode> pathQ = new ArrayList<>();
        findPath(root, p, pathP);
        findPath(root, q, pathQ);
        TreeNode ans = null;
        int n = Math.min(pathP.size(), pathQ.size());
        for (int i = 0; i < n; i++) {
            if (pathP.get(i) == pathQ.get(i)) ans = pathP.get(i);
            else break;
        }
        return ans;
    }

    private boolean findPath(TreeNode cur, TreeNode target, List<TreeNode> path) {
        if (cur == null) return false;
        path.add(cur);
        if (cur == target) return true;
        if (target.val < cur.val && findPath(cur.left, target, path)) return true;
        if (target.val > cur.val && findPath(cur.right, target, path)) return true;
        path.remove(path.size() - 1);
        return false;
    }
}

Optimal

class Solution {
    // Time: O(h), Space: O(1)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode cur = root;
        while (true) {
            if (p.val < cur.val && q.val < cur.val) cur = cur.left;
            else if (p.val > cur.val && q.val > cur.val) cur = cur.right;
            else return cur;
        }
    }
}

Recursive optimal

class SolutionRecursive {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val < root.val && q.val < root.val)
            return lowestCommonAncestor(root.left, p, q);
        if (p.val > root.val && q.val > root.val)
            return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}

---

5. The “Java vs. Others” Edge

• Compare val; comparing TreeNode references works on LeetCode when p/q exist in tree, but BST logic is value-based.
• Iterative saves stack space vs recursion.
• If values were not unique, you must compare node identity — problem here assumes standard BST with distinct keys.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute two paths	O(h)	O(h)	Builds explicit lists
BST walk	O(h)	O(1)	Single pointer; h = height
Recursive walk	O(h)	O(h)	Call stack