In graph theory and computer science, the lowest common ancestor (LCA) of two nodes is the lowest node that has both of them as descendants.

Let’s take an example:

LCA(5, 1) => 3 LCA(5, 4) => 5 LCA(5, 0) => 3 LCA(6, 4) => 5

## Approach #1 : Recursive Algorithm

There are three scenarios for nodes `w`

, `v`

:

- There is another node
`p`

is LCA of`w`

and`v`

`w`

is in the right subtree of`v`

(or`v`

is in the right subtree of`w`

)`w`

is in the left subtree of`v`

(or`v`

is in the left subtree of`w`

)

So we can use a recursive algorithm to find the LCA of left subtree and LCA of right subtree.

```
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL || 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; //scenario #1
if(right != NULL)
return right; //scenario #2
return left; //scenario #3
}
};
```

Time complexity: O(N)

## Approach #2 : Iterative algorithm with Map and Set

We can a `stack`

to traverse the binary tree and use a `map`

record the parent of each node. With this `map`

we could build a `set`

contains all parents of **w**, and check the parents of **v** from bottom to top, return the first common parent.

```
#include <iostream>
#include <set>
#include <map>
#include <stack>
using namespace std;
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
stack<TreeNode*> stack;
map<TreeNode*, TreeNode*> parents;
set<TreeNode*> parents_set;
stack.push(root);
while(!stack.empty()) {
TreeNode* cur = stack.top();
stack.pop();
if(cur->left) {
stack.push(cur->left);
parents[cur->left] = cur;
}
if(cur->right) {
stack.push(cur->right);
parents[cur->right] = cur;
}
}
TreeNode* t = p;
while(t != root) {
parents_set.insert(t);
t = parents[t];
}
t = q;
while(t != root) {
if(parents_set.count(t)) {
return t;
}
t = parents[t];
}
return root;
}
};
```