# Lowest Common Ancestor of a Binary Search Tree

- **Canonical ID**: `lowest-common-ancestor-of-a-bst`
- **Canonical URL**: https://dsacheatsheet.com/problems/lowest-common-ancestor-of-a-bst
- **Difficulty**: medium
- **Patterns**: Trees
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

## 1. Core Invariant / The Trick

Walk down from `root` iteratively using the BST ordering property: if both `p.val` and `q.val` are strictly less than `curr.val`, go left; if both strictly greater, go right; otherwise `curr` is the split point (LCA).

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(H)`
- **Space Complexity**: `O(1)`
- **Proof**: Visits at most one node per level along a single root-to-LCA path with iterative O(1) space.

## 3. Minimal Idiomatic Code

### Python
```python
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    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
    return curr
```

### TypeScript
```typescript
export function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
  let curr = root;
  while (curr && p && q) {
    if (p.val < curr.val && q.val < curr.val) curr = curr.left;
    else if (p.val > curr.val && q.val > curr.val) curr = curr.right;
    else return curr;
  }
  return null;
}
```

### C++
```cpp
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    while (root) {
        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;
    }
    return nullptr;
}
```

### Java
```java
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;
    }
    return null;
}
```

### Go
```go
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    for root != nil {
        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 }
    }
    return nil
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Using general binary tree O(N) LCA ignores the BST ordering invariant and wastes O(H) stack.
- Forgetting a node is a valid descendant of itself (`p == curr` or `q == curr` hits the split condition).

### Follow-ups
- General Binary Tree LCA (not BST): post-order DFS returning non-null when left & right subtrees both find targets.