# LeetCode: 236. Lowest Common Ancestor of a Binary Tree

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

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

**Constraints:**

- The number of nodes in the tree is in the range
`[2, 10`

.^{5}] `-10`

^{9}<= Node.val <= 10^{9}- All
`Node.val`

are.**unique** `p != q`

`p`

and`q`

will exist in the tree.

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if ( root == NULL ) return NULL;
if (root->val == p->val || root->val == q->val) return root;
TreeNode* leftLCA = lowestCommonAncestor(root->left, p, q);
TreeNode* rightLCA = lowestCommonAncestor(root->right, p, q);
if (leftLCA != NULL && rightLCA != NULL) return root;
return leftLCA != NULL ? leftLCA : rightLCA;
}
```

🧠

Github with all the solution including test cases.

Let's break down the code in a simple way:

**This code finds the lowest common ancestor (LCA) of two nodes in a binary tree.**

- It starts at the root of the tree.
- If the root is empty (NULL), it means there's nothing to search, so it returns nothing (NULL).
- If the root's value is equal to either of the two nodes (
`p`

or`q`

), it means one of them is found at this point, so it returns the root as a candidate for the LCA. - It then looks for the LCA in the left and right subtrees of the current node by calling itself recursively.
- If both the left and right subtrees found valid candidates for LCA (not NULL), it means the current node is the lowest common ancestor, so it returns the current node.
- If only one subtree found a valid LCA candidate, it returns that candidate. If both subtrees found nothing, it returns NULL.