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:

file:img/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:

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

Join my Email List for more insights, It's Free!😋

← Lowest Common Ancestor of a Bina... Redis Vs. Memcached →