Coder's Cat

Lowest Common Ancestor of a Binary Tree

2020-04-10

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