> 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/1601-1700/lowest-common-ancestor-of-a-binary-tree-ii.md).

# 1644. Lowest Common Ancestor of a Binary Tree II

### Description

Given the `root` of a binary tree, return *the lowest common ancestor (LCA) of two given nodes,* `p` *and* `q`. If either node `p` or `q` **does not exist** in the tree, return `null`. All values of the nodes in the tree are **unique**.

According to the [**definition of LCA on Wikipedia**](https://en.wikipedia.org/wiki/Lowest_common_ancestor): "The lowest common ancestor of two nodes `p` and `q` in a binary tree `T` is the lowest node that has both `p` and `q` as **descendants** (where we allow **a node to be a descendant of itself**)". A **descendant** of a node `x` is a node `y` that is on the path from node `x` to some leaf node.

### Constraints

* The number of nodes in the tree is in the range `[1, 104]`.
* `-109 <= Node.val <= 109`
* All `Node.val` are **unique**.
* `p != q`

### Approach

### Links

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

### **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/-MUMuvNdvnPbMl1AoONs" 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/-MUMuywFNrLsWdG1-4vc" alt=""></div>

**Output:** 5

**Explanation:** The LCA of nodes 5 and 4 is 5. A node can be a descendant of itself according to the definition of LCA.
{% endtab %}

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

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

**Output:** null

**Explanation:** Node 10 does not exist in the tree, so return null.
{% 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 {
    private int count = 0;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode lca = lcaHelper(root, p, q);
        return (count == 2)? lca: null;
    }
    
    private TreeNode lcaHelper(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        TreeNode left = lcaHelper(root.left, p, q);
        TreeNode right = lcaHelper(root.right, p, q);
        if(root == p || root == q) {
            count++;
            return root;
        }
        if(left != null && right != null) {
            return root;
        }
        return (left == null)? right: left;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*