Lowest Common Ancestor of a Binary Tree

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

1. There is another node `p` is LCA of `w` and `v`
2. `w` is in the right subtree of `v` (or `v` is in the right subtree of `w`)
3. `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;
}
};
``````
Last Updated on