> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/201-300/lowest-common-ancestor-of-a-binary-tree.md).

# 236. Lowest Common Ancestor of a Binary Tree

### Description

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_common_ancestor): “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**).”

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

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/)
* ProgramCreek
* [YouTube](https://youtu.be/13m9ZCB8gjw)

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** root = \[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1

<div align="left"><img src="/files/-MUIOld_IBqDUnyOTx0Y" alt=""></div>

**Output:** 3

**Explanation:** The LCA of nodes 5 and 1 is 3.
{% endtab %}

{% tab title="Example 2" %}
**Input:** root = \[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4

<div align="left"><img src="/files/-MUIOj9mPpLMxpsKyQ_Z" alt=""></div>

**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.
{% endtab %}

{% tab title="Example 3" %}
**Input:** root = \[1, 2], p = 1, q = 2

**Output:** 1
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="TreeNode" %}

```java
// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { 
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
```

{% endtab %}

{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(N), where N is the number of nodes in the binary tree. 
 *    In the worst case we might be visiting all the nodes of the binary tree.
 * Space complexity : O(N). This is because the maximum amount of space 
 *    utilized by the recursion stack would be N since the height of a 
 *    skewed binary tree could be N.
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if(root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null) {
            return root;
        }
        if(left == null && right == null) {
            return null;
        }
        return (left != null)? left: right;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(N), where N is the number of nodes in the binary tree. 
 *    In the worst case we might be visiting all the nodes of the binary tree.
 * Space complexity : O(N). In the worst case space utilized by the stack, 
 *    the parent pointer dictionary and the ancestor set, would be N each, 
 *    since the height of a skewed binary tree could be N.
 */

class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        // Stack for tree traversal
        Deque<TreeNode> stack = new ArrayDeque<>();

        // HashMap for parent pointers
        Map<TreeNode, TreeNode> parent = new HashMap<>();

        parent.put(root, null);
        stack.push(root);

        // Iterate until we find both the nodes p and q
        while (!parent.containsKey(p) || !parent.containsKey(q)) {

            TreeNode node = stack.pop();

            // While traversing the tree, keep saving the parent pointers.
            if (node.left != null) {
                parent.put(node.left, node);
                stack.push(node.left);
            }
            if (node.right != null) {
                parent.put(node.right, node);
                stack.push(node.right);
            }
        }

        // Ancestors set() for node p.
        Set<TreeNode> ancestors = new HashSet<>();

        // Process all ancestors for node p using parent pointers.
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }

        // The first ancestor of q which appears in
        // p's ancestor set() is their lowest common ancestor.
        while (!ancestors.contains(q))
            q = parent.get(q);
        return q;
    }

}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*