# Lowest Common Ancestor of a Binary Search Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree)
Canonical: https://scaleengineer.com/dsa/problems/lowest-common-ancestor-of-a-binary-search-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree, Binary Search Tree
**Companies:** [Google](https://scaleengineer.com/companies/google), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Oracle](https://scaleengineer.com/companies/oracle), [Samsung](https://scaleengineer.com/companies/samsung), [Yandex](https://scaleengineer.com/companies/yandex), [X](https://scaleengineer.com/companies/x)
---
## Problem
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](https://en.wikipedia.org/wiki/Lowest%5Fcommon%5Fancestor): “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:**

![](https://assets.glich.co/dsa/lowest-common-ancestor-of-a-binary-search-tree/image0.png) 

**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:**

![](https://assets.glich.co/dsa/lowest-common-ancestor-of-a-binary-search-tree/image1.png) 

**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.

# Approaches
## Recursive DFS Approach
This approach uses a recursive depth-first search to traverse the binary search tree and find the lowest common ancestor. It doesn't utilize the BST property and treats it as a regular binary tree.
**Time:** O(N) where N is the number of nodes in the tree as we might need to visit all nodes · **Space:** O(H) where H is the height of the tree due to recursive call stack
**Pros:** Works for any binary tree, not just BST; Simple to understand and implement; Can be extended to find LCA of more than two nodes
**Cons:** Doesn't utilize BST properties; Uses more space due to recursive calls; Visits unnecessary nodes
### Explanation
The recursive approach works by traversing the tree and checking if the current node is either p or q. If we find either p or q, we return that node. If we get non-null values from both left and right subtrees, the current node is the LCA. If we get a non-null value from only one side, we propagate that up.

```java
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case: if root is null or equals either p or q
        if (root == null || root == p || root == q) {
            return root;
        }
        
        // Recursively search in left and right subtrees
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // If both left and right are non-null, root is the LCA
        if (left != null && right != null) {
            return root;
        }
        
        // Return non-null value
        return left != null ? left : right;
    }
}
```
### Algorithm
1. If root is null or equals either p or q, return root
2. Recursively search in left subtree
3. Recursively search in right subtree
4. If both left and right searches return non-null values, current node is LCA
5. Otherwise, return the non-null value from either left or right

## Iterative BST Property Approach
This approach utilizes the BST property where all left subtree values are less than the node and all right subtree values are greater than the node. We can use this to efficiently find the LCA without recursion.
**Time:** O(H) where H is the height of the tree. In balanced BST, this becomes O(log N) · **Space:** O(1) as only a constant amount of extra space is used
**Pros:** Utilizes BST properties for efficient traversal; No recursion needed; Only visits nodes in the path to LCA; Constant space complexity
**Cons:** Only works for BST, not for general binary trees; Requires tree to maintain BST property
### Explanation
Since this is a BST, we can use its properties to find the LCA more efficiently. If both p and q are greater than the current node, LCA must be in the right subtree. If both are smaller, LCA must be in the left subtree. If they're on different sides (or one equals the current node), we've found the LCA.

```java
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode current = root;
        
        while (current != null) {
            // If both p and q are greater than current, go right
            if (p.val > current.val && q.val > current.val) {
                current = current.right;
            }
            // If both p and q are less than current, go left
            else if (p.val < current.val && q.val < current.val) {
                current = current.left;
            }
            // We found the split point, this is the LCA
            else {
                return current;
            }
        }
        return null;
    }
}
```
### Algorithm
1. Start from root node
2. While current node is not null:
   - If both p and q are greater than current, move to right child
   - If both p and q are less than current, move to left child
   - Otherwise, current node is the LCA

# Solutions
### CSharp

```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode LowestCommonAncestor ( TreeNode root , TreeNode p , TreeNode q ) { while ( true ) { if ( root . val < Math . Min ( p . val , q . val )) { root = root . right ; } else if ( root . val > Math . Max ( p . val , q . val )) { root = root . left ; } else { return root ; } } } }
```

### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode lowestCommonAncestor ( TreeNode root , TreeNode p , TreeNode q ) { while ( true ) { if ( root . val < Math . min ( p . val , q . val )) { root = root . right ; } else if ( root . val > Math . max ( p . val , q . val )) { root = root . left ; } else { return root ; } } } }
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution : def lowestCommonAncestor ( self , root : 'TreeNode' , p : 'TreeNode' , q : 'TreeNode' ) -> 'TreeNode' : while 1 : if root . val < min ( p . val , q . val ): # no =, so root is p or q is in else block root = root . right elif root . val > max ( p . val , q . val ): root = root . left else : return root ############ class Solution : def lowestCommonAncestor ( self , root , p , q ): if root is None : return root if root . val > max ( p . val , q . val ): return self . lowestCommonAncestor ( root . left , p , q ) elif root . val < min ( p . val , q . val ): return self . lowestCommonAncestor ( root . right , p , q ) else : return root ############ class Solution ( object ): def lowestCommonAncestor ( self , root , p , q ): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ a , b = sorted ([ p . val , q . val ]) while not a <= root . val <= b : if a > root . val : root = root . right else : root = root . left return root
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode * lowestCommonAncestor ( TreeNode * root , TreeNode * p , TreeNode * q ) { while ( 1 ) { if ( root -> val < min ( p -> val , q -> val )) { root = root -> right ; } else if ( root -> val > max ( p -> val , q -> val )) { root = root -> left ; } else { return root ; } } } };
```