> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/least-common-ancestor.md).

# Least Common Ancestor

Find the lowest common ancestor in an unordered binary tree given two values in the tree.

> **Lowest common ancestor :** the lowest common ancestor (LCA) of two nodes `v` and `w` in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both `v` and `w` as descendants. 

**Example :**

```

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2_     0        8
         /   \
         7    4
```

For the above tree, the LCA of nodes `5` and `1` is `3`.

> **LCA** = Lowest common ancestor 

Please note that LCA for nodes `5` and `4` is `5`.

> * You are given 2 values. Find the lowest common ancestor of the two nodes represented by `val1` and `val2`
> * No guarantee that `val1` and `val2` exist in the tree. If one value doesn’t exist in the tree then return -1.
> * There are no duplicate values.
> * You can use extra memory, helper functions, and can modify the node struct but, you can’t add a parent pointer.

```java
class Solution {
    boolean foundP = false;
    boolean foundQ = false;

    public int lowestCommonAncestor(TreeNode root, int p, int q) {
        if (root == null)
            return -1;
        if (root.val == p || root.val == q) {
            foundP = root.val == p ? true : foundP;
            foundQ = root.val == q ? true : foundQ;
        }
        int left = lowestCommonAncestor(root.left, p, q);
        int right = lowestCommonAncestor(root.right, p, q);
        if (root.val == p || root.val == q) {
            return root.val;
        } else {
            if (left != -1 && right != -1)
                return root.val;
            else if (left != -1)
                return left;
            else if (right != -1)
                return right;
            return -1;
        }
    }

    public int lca(TreeNode root, int p, int q) {
        foundP = false;
        foundQ = false;
        int ans = lowestCommonAncestor(root, p, q);
        if (foundP && foundQ)
            return ans;
        return -1;
    }
}
```