> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/trees/binary-tree/medium/236.-lowest-common-ancestor-of-a-binary-tree-235.-lowest-common-ancestor-of-a-binary-search-tree.md).
# 236. Lowest Common Ancestor of a Binary Tree / 235. Lowest Common Ancestor of a Binary Search Tree
## Problem Statement
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).”
**Example 1:**
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:**
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.
## Intuition
```
Approach:
When we encounter p and q we return them
Using DFS
Whenever we find, left and right not returning null on both
We return that root
Else we return the not null thing
```
### Links
### Video Links
### Approach 1:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == p or root == q or root == nullptr)
return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left != nullptr and right != nullptr)
return root;
return left == nullptr ? right : left;
}
};
```
{% endcode %}
### Approach 2:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Approach 3:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Approach 4:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Similar Problems
###