DEV Community is a community of 786,090 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Nic

Posted on • Originally published at coderscat.com on

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

The post Lowest Common Ancestor of a Binary Tree appeared first on Coder's Cat.