Lowest Common Ancestor of a Binary Search Tree

• Difficulty: Medium
• Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree
• Link: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Problem Description

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q will exist in the BST.

Solution

1. Problem Deconstruction

Technical Description:
Given a binary search tree (BST) with unique integer-valued nodes and two distinct nodes p and q guaranteed to exist in the BST, find the lowest common ancestor (LCA) node. The LCA is defined as the deepest node in the BST that has both p and q as descendants, where a node is considered a descendant of itself. The BST property holds: for any node, all values in its left subtree are strictly less than its value, and all values in its right subtree are strictly greater.

Beginner Description:
Imagine a family tree where each person has at most two children: a left child (younger/smaller ID) and a right child (older/larger ID). Given two people in this tree, find their closest common ancestor – the person furthest down the tree who is an ancestor to both. A person counts as their own ancestor.

Mathematical Description:
Let $T$ be a BST with root $r$. For nodes $p$ and $q$, the LCA $x$ satisfies:

1. $x$ is on the path from $r$ to $p$ and $r$ to $q$
2. $\text{depth}(x)$ is maximized
3. $\text{sign}(p.\text{val} - x.\text{val}) \neq \text{sign}(q.\text{val} - x.\text{val})$ or $x = p$ or $x = q$

Constraint Analysis:

1. Nodes in [2, 10⁵]:
   • Eliminates O(n²) brute-force (10¹⁰ operations at 10⁵ nodes).
   • Worst-case skewed tree height is 10⁵ → recursion depth must be managed.
2. Node.val ∈ [-10⁹, 10⁹]:
   • Comparisons won’t overflow in modern languages (Python/Java use big integers).
   • Values are unique → no equality checks needed.
3. p ≠ q and both exist:
   • No need to handle missing nodes or identical inputs.
   • Edge case: One node is the direct ancestor of the other (e.g., parent-child).

Hidden Edge Cases:

• Root is LCA (p and q in different subtrees)
• LCA is p or q (one node is ancestor of the other)
• Skewed tree (worst-case O(n) time for unbalanced BST)
• p or q is root (immediate termination)

---

2. Intuition Scaffolding

Real-World Metaphor:
Organizational hierarchy where each manager (node) has two teams: left (lower employee IDs) and right (higher IDs). Finding the lowest common manager for two employees is like traversing upwards until their reporting paths converge.

Gaming Analogy:
Skill trees in RPGs where left branches are defensive skills (lower values) and right branches are offensive (higher values). The LCA is the most advanced shared prerequisite skill needed for two given skills.

Math Analogy:
Finding the supremum of the lower bounds (or infimum of the upper bounds) for the values of p and q in the BST’s path topology.

Common Pitfalls:

1. Global min/max trap: Assuming LCA is root when p and q span root’s value (correct) but forcing full tree traversal.
2. One-sided search: Only checking left/right subtree without BST property optimization.
3. Depth miscalculation: Storing depths unnecessarily when BST property enables value-based decisions.
4. Overlooking self-ancestry: Not considering a node as its own descendant (e.g., returning parent instead of p when p is ancestor of q).
5. Recursion depth: Stack overflow in skewed trees for recursive solutions (10⁵ nested calls).

---

3. Approach Encyclopedia

Approach 1: Brute Force (Path Recording)

Pseudocode:

def find_path(root, target):  
    path = []  
    while root:  
        path.append(root)  
        if target.val < root.val: root = root.left  
        elif target.val > root.val: root = root.right  
        else: return path  
    return []  # Not found (but guaranteed to exist)  

def lca(root, p, q):  
    path_p = find_path(root, p)  # O(h)  
    path_q = find_path(root, q)  # O(h)  
    lca_node = root  
    for i in range(min(len(path_p), len(path_q)):  
        if path_p[i] == path_q[i]:  
            lca_node = path_p[i]  
        else:  
            break  
    return lca_node  

Complexity Proof:

• Time: O(h_p + h_q) where h = height. Worst-case O(2h) = O(h).
• Space: O(h) to store paths.
  Visualization:

Path_p: [6, 2]      // For p=2  
Path_q: [6, 2, 4]   // For q=4  
LCA: 2 (last common node at index 1)  

Approach 2: Recursive BST Property Exploitation

Pseudocode:

def lca(root, p, q):  
    if not root: return None  
    if p.val < root.val and q.val < root.val:  
        return lca(root.left, p, q)  
    elif p.val > root.val and q.val > root.val:  
        return lca(root.right, p, q)  
    else:  
        return root  # p and q straddle root or root is p/q  

Complexity Proof:

• Time: O(h). Each recursion level visits one node.
• Space: O(h) for call stack (worst-case skewed tree).
  Visualization:

Example: p=2, q=4  
Start at 6: 2<6 and 4<6 → recurse left to 2  
At 2: 2==2 → return 2 (LCA)  

Approach 3: Iterative BST Property Exploitation (Optimal)

Pseudocode:

def lca(root, p, q):  
    curr = root  
    while curr:  
        if p.val < curr.val and q.val < curr.val:  
            curr = curr.left  
        elif p.val > curr.val and q.val > curr.val:  
            curr = curr.right  
        else:  
            return curr  

Complexity Proof:

• Time: O(h). Each iteration moves one level.
• Space: O(1). Constant extra space.
  Visualization:

[6,2,8,0,4,7,9], p=2, q=4:  
  Start: curr=6 → 2<6 and 4<6? True → curr=2  
  At 2: 2==2 → return 2  

---

4. Code Deep Dive

Optimal Solution (Iterative):

class Solution:  
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':  
        curr = root  # Initialize traversal pointer  
        while curr:  
            # Both nodes in left subtree  
            if p.val < curr.val and q.val < curr.val:  
                curr = curr.left  
            # Both nodes in right subtree  
            elif p.val > curr.val and q.val > curr.val:  
                curr = curr.right  
            # LCA found:  
            # Case 1: p and q straddle curr (one in left, one in right)  
            # Case 2: curr is p or q  
            else:  
                return curr  

Edge Case Handling:

• Example 1 (p=2, q=8):
  6 is root → 2<6 and 8>6 → return 6 (straddling).
• Example 2 (p=2, q=4):
  At 6: both <6 → move left to 2.
  At 2: 2==2 → return 2 (curr is p).
• Example 3 (p=2, q=1):
  At root 2: q=1<2 → no move → return 2 (curr is p).

---

5. Complexity War Room

Hardware-Aware Analysis:

• 10⁵ nodes (skewed tree):
  • Time: 10⁵ iterations (≈ 0.2ms in C++, 20ms in Python)
  • Space: 8 bytes (single pointer) → fits in L1 cache (64KB).
• Balanced tree (h=log₂(10⁵)≈17):
  • Time: 17 iterations (negligible).

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force (Path)	O(h)	O(h)	8/10	⚠️ Acceptable
Recursive	O(h)	O(h)	9/10	⚠️ Stack risk
Iterative	O(h)	O(1)	10/10	✅ Optimal

---

6. Pro Mode Extras

Variants:

1. LCA for k nodes in BST:

   def lca_k(root, nodes):  
       min_val = min(n.val for n in nodes)  
       max_val = max(n.val for n in nodes)  
       curr = root  
       while curr:  
           if max_val < curr.val:  
               curr = curr.left  
           elif min_val > curr.val:  
               curr = curr.right  
           else:  
               return curr  
   

2. LCA with parent pointers (no root):
   • Compute depths of p and q via parent traversal.
   • Move deeper node up until depths equal.
   • Move both up until they meet (O(h) time, O(1) space).

Interview Cheat Sheet:

• First Mention: Time/space complexity.
• Key Insight: BST property allows directional decisions (no need for full subtrees).
• Verbalize Cases:
  1. p and q both left → go left
  2. both right → go right
  3. else: current node is LCA
• Test Cases:
  • p is ancestor of q
  • q is ancestor of p
  • p and q in different subtrees of root
  • p or q is root