Lowest Common Ancestor of a Binary Tree
Tags: leetcode, algorithms
Published: 2020-04-11 15:25:36

---
title: Lowest Common Ancestor of a Binary Tree
published: true
date: 2020-04-10 15:47:00 UTC
tags: LeetCode,Algorithms
canonical_url: https://coderscat.com/lowest-common-ancestor-of-a-binary-tree
---

In graph theory and computer science, [the lowest common ancestor (LCA)](https://en.wikipedia.org/wiki/Lowest_common_ancestor) of two nodes is the lowest node that has both of them as descendants.

Let’s take an example:

![CAPTURE-2020_04_10_find-the-lowest-common-ancestor-of-a-binary-tree.org_20200410_224917.png](https://coderscat.com/wp-content/uploads/CAPTURE-2020_04_10_find-the-lowest-common-ancestor-of-a-binary-tree.org_20200410_224917.png)

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

```cpp
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 : Iteractive 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.

```cpp
#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;        
    }
};
```

The post [Lowest Common Ancestor of a Binary Tree](https://coderscat.com/lowest-common-ancestor-of-a-binary-tree) appeared first on [Coder's Cat](https://coderscat.com).