TreeMediumO(h) time · O(h) space

LCA of BST

Mahabharata — The BST Lineage — Using Order to Find the Common Ancestor Faster

BST में LCA — आदेश से मार्ग मिलता। दोनों छोटे — बाएं; दोनों बड़े — दाएं; अन्यथा — यही LCA॥

*LCA in BST — order shows the way. Both smaller — go left; both larger — go right; otherwise — this is the LCA.*

The Story

Find the Lowest Common Ancestor of two nodes p and q in a **Binary Search Tree**. Unlike the general binary tree LCA (tr-12), we can exploit the BST property for an O(h) solution.

For BST `[6,2,8,0,4,7,9,null,null,3,5]`, p=2, q=8: LCA=6. For same BST, p=2, q=4: LCA=2.

**BST Property-Based LCA:** At any node, the LCA is: - The current root, if p and q are on different sides (or one equals root) - In the left subtree, if both p.val and q.val < root.val - In the right subtree, if both p.val and q.val > root.val

```java public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q); // Both in left if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q); // Both in right return root; // Split point (or one equals root) → LCA! } ```

**Iterative (O(1) space):** ```java while (true) { 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; } ```

Trace p=2, q=8 in BST root=6: - Both on opposite sides of 6 → return 6 ✓

Trace p=2, q=4 in BST root=6: - Both < 6 → go left to 2 - At 2: p=2==root, or 4>2 so split here → return 2 ✓

The General Binary Tree LCA (tr-12)

Use the O(n) post-order bubble-up approach from tr-12. Ignores BST property.

java

// General LCA (tr-12) works but O(n). BST-specific is O(h).
public TreeNode lowestCommonAncestorGeneral(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestorGeneral(root.left, p, q);
    TreeNode right = lowestCommonAncestorGeneral(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

The BST Split-Point LCA Wisdom

Iterative: if both p,q < root → go left; if both > root → go right; else return root. O(h).

java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (true) {
        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;
    }
}

Step-by-Step Walkthrough

p=7, q=9 in BST with root=6,right=8,right.left=7,right.right=9
Both > 6 → go right to 8. 7<8 and 9>8 → split at 8 → LCA=8 ✅

Deep Insight

**BST LCA vs General LCA:** - General (tr-12): O(n) DFS, no BST property needed - BST (tr-14): O(h) → O(log n) for balanced BST

**The 'split point' insight:** In a BST, p and q are in the same subtree if both < root or both > root. The moment they diverge (one on each side, or one equals root), the current node IS the LCA — the deepest node where their paths from root first diverge.

**One equals root edge case:** If p.val == root.val, then p IS in the BST as the current node. The condition `else return root` handles this: neither 'both < root' nor 'both > root' → split condition triggered → return root = p → LCA is p itself (correct since p is an ancestor of q which is in p's subtree).

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n)	O(n)	General LCA, ignores BST
Optimal	O(h)	O(1)	Iterative, O(log n) balanced, O(n) skewed

Pattern Recognition

✅ LCA in BST: O(h) via split-point logic
✅ Both < root → left; both > root → right; else return root
✅ Iterative for O(1) space
✅ Much faster than general LCA O(n)

**LeetCode Trigger Phrases:**
→ "LCA of BST" (explicit BST given)
→ When BST property is mentioned, use O(h) approach
→ Split-point: when p and q diverge

Bhagavad Gita 6.30

यो मां पश्यति सर्वत्र सर्वं च मयि पश्यति। तस्याहं न प्रणश्यामि स च मे न प्रणश्यति॥

One who sees Me everywhere and sees everything in Me — I am never lost to that person, and that person is never lost to Me.

Connection: The LCA in a BST is the precise point where two paths of descent first converge — where two warriors share their deepest common origin. The BST's ordering ensures we can find this meeting point in O(h) steps rather than searching the entire tree: just follow the divergence. Like the divine who is never lost to those who see the shared origin in everything, the LCA algorithm directly navigates to that convergence point.