# Lowest Common Ancestor of a Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/lowest-common-ancestor-of-a-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Flipkart](https://scaleengineer.com/companies/flipkart), [Intuit](https://scaleengineer.com/companies/intuit), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Myntra](https://scaleengineer.com/companies/myntra), [Oracle](https://scaleengineer.com/companies/oracle), [Wix](https://scaleengineer.com/companies/wix), [Yandex](https://scaleengineer.com/companies/yandex), [Salesforce](https://scaleengineer.com/companies/salesforce), [BitGo](https://scaleengineer.com/companies/bitgo), [GE Healthcare](https://scaleengineer.com/companies/ge-healthcare), [MongoDB](https://scaleengineer.com/companies/mongodb), [Snapdeal](https://scaleengineer.com/companies/snapdeal)
---
## Problem
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

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-tree/image0.png) 

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

**Example 2:**

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

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

**Example 3:**

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

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

# Approaches
## Brute Force Path Finding
Find paths from root to both nodes p and q, then compare the paths to find the last common node.
**Time:** O(N) where N is the number of nodes in the tree. We need to traverse the tree twice to find paths. · **Space:** O(H) where H is the height of the tree, needed to store the paths
**Pros:** Easy to understand and implement; Works for any binary tree; No extra space needed except for storing paths
**Cons:** Requires two tree traversals; Needs extra space to store paths; Not very efficient for large trees
### Explanation
This approach involves two steps:

1. First, we find the path from root to both nodes p and q by doing a DFS traversal and storing the paths.
2. Then we compare both paths to find the last common node which will be our LCA.

```java
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path1 = new ArrayList<>();
        List<TreeNode> path2 = new ArrayList<>();
        
        findPath(root, p, path1);
        findPath(root, q, path2);
        
        TreeNode lca = null;
        int i = 0;
        while (i < path1.size() && i < path2.size()) {
            if (path1.get(i) == path2.get(i)) {
                lca = path1.get(i);
            }
            i++;
        }
        return lca;
    }
    
    private boolean findPath(TreeNode root, TreeNode node, List<TreeNode> path) {
        if (root == null) return false;
        
        path.add(root);
        if (root == node) return true;
        
        if (findPath(root.left, node, path) || findPath(root.right, node, path)) {
            return true;
        }
        path.remove(path.size() - 1);
        return false;
    }
}
```
### Algorithm
1. Create two lists to store paths from root to p and q
2. Use DFS to find path from root to p
3. Use DFS to find path from root to q
4. Compare both paths to find the last common node
5. Return the last common node as LCA

## Single Pass DFS Solution
Use a single DFS traversal to find LCA by checking if current node is p or q and returning accordingly.
**Time:** O(N) where N is the number of nodes in the tree. We only need to visit each node once. · **Space:** O(H) where H is the height of the tree, needed for recursion stack
**Pros:** Single pass solution; No extra space needed except recursion stack; More efficient than brute force approach; Clean and elegant solution
**Cons:** Recursive solution might cause stack overflow for very deep trees; Not as intuitive as the path finding approach
### Explanation
This approach uses a single DFS traversal:

1. If the current node is null or equals to p or q, return current node
2. Recursively search in left and right subtrees
3. If both left and right returns are non-null, current node is LCA
4. If one of them is null, return the non-null value

```java
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case
        if (root == null || root == p || root == q) {
            return root;
        }
        
        // 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, we found our 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 p or q, return root
2. Recursively search in left subtree
3. Recursively search in right subtree
4. If both recursive calls return non-null, current node is LCA
5. Otherwise return the non-null value

# Solutions
### 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 ) { if ( root == null || root == p || root == q ) return root ; TreeNode left = lowestCommonAncestor ( root . left , p , q ); TreeNode right = lowestCommonAncestor ( root . right , p , q ); if ( left == null ) return right ; if ( right == null ) return left ; return root ; } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */ var lowestCommonAncestor =
  function (root, p, q) {
    if (!root || root == p || root == q) return root;
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    if (!left) return right;
    if (!right) return 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 ) { if ( ! root || root == p || root == q ) return root ; TreeNode * left = lowestCommonAncestor ( root -> left , p , q ); TreeNode * right = lowestCommonAncestor ( root -> right , p , q ); if ( left && right ) return root ; return left ? left : right ; } };
```

### 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' : if root is None or root == p or root == q : return root left = self . lowestCommonAncestor ( root . left , p , q ) right = self . lowestCommonAncestor ( root . right , p , q ) return root if left and right else ( left or right ) ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution ( object ): def lowestCommonAncestor ( self , root , p , q ): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if not root : return root left = self . lowestCommonAncestor ( root . left , p , q ) right = self . lowestCommonAncestor ( root . right , p , q ) if left and right : return root if root == p or root == q : return root if left : return left if right : return right return None
```