Lowest Common Ancestor of a Binary Tree

#leetcode #algorithms

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

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