Finding the Lowest Common Ancestor of a Binary Tree
Basics of SQL
12 Hrs. duration
12 Modules
2600+ Learners
Start Learning
A Binary tree, a nonlinear data structure, is a fundamental concept in computer science. In this article, we will delve into its practical application by using Java to find the lowest common ancestor in a Binary tree, a problem that often arises in real-world scenarios.
Introduction
In a Binary tree, the lowest common ancestor is the lowest node in the tree that has both n1 and n2 as descendants of the same ancestor. We have to find the common ancestor of those descendants that shared the ancestor of n1 and n2 located farthest from the root. We will explore methods to find the LCA in a binary tree, discussing their time and space complexities.
Problem Statement
Given a binary tree and two nodes, the task is to find their lowest Common Ancestor. Let’s consider the following binary tree, for example.
Example
In this tree:
The LCA of nodes 4 and 5 is 2
The LCA of nodes 4 and 6 is 1.
The LCA of nodes 7 and 8 is 5.
Constraints
Let’s discuss the constraints of this problem
0 < n < 10 ^ 5, where n is the number of nodes.
0 < node.val < 10 ^ 9
Approach 1: By Storing Root n1 and Root To n2 Paths
One of the methods to find the Lowest Common Ancestor of two nodes in a binary tree is by storing the paths from the root to each of the two nodes and then comparing these paths to find the last common node. Because In any tree data structure, a unique path exists between any two nodes. Let’s see the algorithm of the Lowest Common Ancestor.
Algorithm
To find the lowest common ancestor of a binary tree, we will perform the following steps in our source code.
We must store the path from the root to n1 in a list. Let it be path1.
We must also store the path from the root to n2 in a list. Let it be path2.
After getting both obtained paths, traverse the node path until the node path is common and return the node that occurs just before the mismatch.
Let’s see “how we can find the path from the root node to the target node”.
We have to define the list of integers, such as the name of the list path. Then, pass it to a boolean-type recursive function, findPath, which accepts three arguments: root,val, and path.
If the root is null, then return false.
Push root.val in the path list.
If our root.val is equal to val, then return true, as we’ve found that the desired node is any of the subtrees.
We must remove the element at the last position in our path list.
In the list, if nothing is worked out, then return false.
Dry Run
We will dry-run this approach using this given tree before implementing this algorithm in a programming language.
Tree
Find the Lowest Common Ancestor of (4,5)
Find the root node to the node with value 4. The first path will be
[1 -> 2 -> 4]
Find the path from the root node to the node with value 5. path2
[1->2->5]
Now, we will traverse both paths until we find the same path. Since we found a second mismatch, we will return the value just before the second index, which is 2.
Find the Lowest Common Ancestor of (7,4)
Find the path from the root node to the node with value 7. The first Path will be
[1->2->4->7]
Find the path from the root node to the node with value 5. The second path will be
[1-> 2->4]
Now, we must traverse both lists until the path is the same. Here, we will read the last index of path1, but if we do not find any mismatch, we will return the node at the last index of path1.
Find the Lowest Common Ancestor of (5,8)
Find the path from the root node to the node with value 5. The path will be
[1-> 2->4]
Find the path from the root node to the node with value 8. The path will be
[1->3-> 7->8]
Once again, we must traverse both path lists until the path has the same value. At the 1st index, we encounter a mismatch in paths, so we will return the node present at the 0th index 1.
Java Implementation
import java.util.*;
class BinaryTree{
static List<Integer> path1 ;
static List<Integer> path2 ;
static boolean findPath(Node root, int value, List<Integer> path){
if(root == null){
return false ;
}
path.add(root.value) ;
if(root.value == value){
return true ;
}
if(findPath(root.left,value,path)|| findPath(root.right, value, path)){
return true ;
}
path.remove(path.size() -1) ;
return false ;
}
static int findLCA(Node root, int node1, int node2){
if(!findPath(root,node1,path1)|| !findPath(root, node2,path2)){
System.out.println("Pleae enter valid input");
return -1 ;
}
int index ;
for( index = 0;index< path1.size() && index < path2.size();index++){
if(path1.get(index) != path2.get(index)){
break ;
}
}
return path1.get(index -1) ;
}
static int LCA (Node root, int node1, int node2){
path1 = new ArrayList<>() ;
path2 = new ArrayList<>() ;
return findLCA(root, node1, node2) ;
}
public static void main(String args[]){
Node root = new Node(1) ;
root.left = new Node(2) ;
root.left.left =new Node(4) ;
root.left.left.right = new Node(7) ;
root.left.right = new Node(5) ;
root.right = new Node(3) ;
root.right.right = new Node(6) ;
root.right.right.left = new Node(8) ;
root.right.right.right = new Node(10) ;
System.out.println("LCA of 4 and 5 is "+LCA(root, 4, 5)) ;
System.out.println("LCA of 7 and 4 is "+ LCA(root,7,4));
System.out.println("LCA of 5 and 8 is "+ LCA(root,5,8)) ;
System.out.println("LCA of 5 and 10 is "+LCA(root,5,10)) ;
}
}
class Node {
int value ;
Node left,right ;
Node(int value){
this.value = value ;
}
}
Output
LCA of 4 and 5 is 2
LCA of 7 and 4 is 4
LCA of 5 and 8 is 1
LCA of 5 and 10 is 1
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
class Node{
public:
int val;
Node *left, *right;
Node(int Val){
val = Val;
left = nullptr;
right = nullptr;
}
};
vector<int> path1;
vector<int> path2;
bool findPath (Node *root, int val,
vector<int> &path){
if (root == nullptr)
return false;
path.push_back(root->val);
if(root->val == val){
return true;
}
if(findPath(root->left, val, path)
|| findPath(root->right, val, path)){
return true;
}
path.pop_back();
return false;
}
int findLCA(Node *root, int n1, int n2){
if (!findPath(root, n1, path1)
|| !findPath(root, n2, path2)){
cout << "Please enter valid input" << endl;
return -1;
}
int ind;
for (ind = 0; ind < path1.size()
&& ind < path2.size(); ind++){
// If there is a mismatch break the loop.
if(path1[ind] != path2[ind])
break;
}
return path1[ind - 1];
}
static int LCA(Node *root, int n1, int n2) {
path1.clear();
path2.clear();
return findLCA(root, n1, n2);
}
int main() {
Node *root = new Node(1);
root->left = new Node(2);
root->left->left = new Node(4);
root->left->left->right = new Node(7);
root->left->right = new Node(5);
root->right = new Node(3);
root->right->right = new Node(6);
root->right->right->left = new Node(8);
root->right->right->right = new Node(9);
cout << "LCA of 4 and 5 is " <<
LCA (root, 4, 5) << endl;
cout << "LCA of 7 and 4 is " <<
LCA (root, 7, 4) << endl;
cout << "LCA of 5 and 8 is " <<
LCA (root, 5, 8) << endl;
cout << "LCA of 5 and 10 is " <<
LCA (root, 5, 10) << endl;
}
Output
LCA of 4 and 5 is 2
LCA of 7 and 4 is 4
LCA of 5 and 8 is 1
LCA of 5 and 10 is Please enter valid input
-1
Python Implementation
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
path1 = []
path2 = []
def findPath (root, value, path):
if (root == None):
return False
path.append(root.value)
if(root.value == value):
return True
if(findPath(root.left, value, path)
or findPath(root.right, value, path)):
return True
path.pop()
return False
def findLCA(root, n1, n2):
if (findPath(root, n1, path1) == False
or findPath(root, n2, path2) == False):
print("Please enter valid input")
return -1
ind = 0
while( ind < len(path1) and ind < len(path2)):
if(path1[ind] != path2[ind]):
break
ind+=1
return path1[ind - 1]
# Function to find the Lowest common ancestor
def LCA(root, n1, n2):
global path1, path2
path1 = []
path2 = []
return findLCA(root, n1, n2)
root = Node(1)
root.left = Node(2)
root.left.left = Node(4)
root.left.left.right = Node(7)
root.left.right = Node(5)
root.right = Node(3)
root.right.right = Node(6)
root.right.right.left = Node(8)
root.right.right.right = Node(9)
print("LCA of 4 and 5 is ", LCA (root, 4, 5))
print("LCA of 7 and 4 is ", LCA (root, 7, 4))
print("LCA of 5 and 8 is ", LCA (root, 5, 8))
print("LCA of 5 and 10 is ", LCA (root, 5, 10))
Output
LCA of 4 and 5 is 2
LCA of 7 and 4 is 4
LCA of 5 and 8 is 1
Please enter valid input
LCA of 5 and 10 is -1
Complexity Analysis
Time Complexity: In the worst case. We have to traverse the whole binary tree. It requires O(n) time to find the Lowest Common Ancestor.
Space Complexity: The overall space of the binary tree is O(h).
Approach 2 – Using Single Traversal (Recursive Approach)
In the previous approach, we used traversing twice (once to find the path from the root node to the target node and from the root node to the 2nd target node. Now, we will optimise this approach so that it requires only one traversal to find the lowest ancestor of a binary tree with the lowest common ancestor.
Algorithm
Let’s look at the algorithm used to find the lowest common ancestor of a binary tree, as follows.
For example, let’s define two boolean values, b1 and b2, which will help us verify whether both keys provided as the input exist in a binary tree.
Then, a recursive function named find LowestCommontAncesstor is defined, and it accepts three arguments: node, n1, and n2.
In this function, you must define the base condition that returns null whenever the node is null.
Define a variable answer that initializes it to be null.
You must check if the node’s value equals n1, make b1 true, and set the node to the answer.
Otherwise, you have to check if node.value is equal to n2, make b2 true, and assign the node to answer.
Recursive the left and right subtree and store their return values in the variables. We can define variables leftAnswer and righAnswer.
If we find that the answer is no longer equal to null, then we will return it.
Otherwise, If we find that both the leftAns and rightAns are not null, we will return the node.
Both values b1 and b2 are true or not. If they both are true, we will return the node value returned by the recursive function. Otherwise, we will return -1.
Java Implementation
class BinaryTree2{
static boolean b1,b2 ;
static Node findLCA(Node node, int node1,int node2){
if(node == null)
return null ;
Node answer = null ;
if(node.value == node1){
b1 = true ;
answer = node ;
}
else if (node.value == node2){
b2 = true ;
answer = node ;
}
Node leftAnswer = findLCA(node.left, node1,node2) ;
Node rightAnswer = findLCA(node.right,node1,node2) ;
if(answer != null)
return answer ;
if(leftAnswer != null && rightAnswer != null){
return node ;
}
return leftAnswer !=null ? leftAnswer : rightAnswer ;
}
static int LowestCommmonAncestor(Node root, int node1, int node2){
b1 = false ;
b2 = false ;
Node lca = findLCA(root, node1, node2) ;
if(b1 && b2){
return lca.value ;
}
System.out.println("Please Enter Valid Input") ;
return -1 ;
}
public static void main(String args[]){
Node root = new Node(101) ;
root.left = new Node(102) ;
root.left.left = new Node(104) ;
root.left.left.right = new Node(107) ;
root.left.left.right = new Node(105) ;
root.right = new Node(103) ;
root.right.right = new Node(106);
root.right.right.left = new Node(108) ;
root.right.right.right = new Node(109) ;
System.out.println("Lowest Common Ancestor of 4 and 5 is "+LowestCommmonAncestor(root,104,105)) ;
System.out.println("Lowest Common Ancestor of 7 and 4 is"+LowestCommmonAncestor(root,107,104)) ;
System.out.println("Lowest Common Ancestor of 5 and 8 is "+LowestCommmonAncestor(root,105,108)) ;
System.out.println("Lowest Common Ancestor of 5 and 10 is "+LowestCommmonAncestor(root,105,10)) ;
}
}
class Node {
int value ;
Node left, right ;
Node(int value){
this.value = value ;
}
}
Output
Lowest Common Ancestor of 4 and 5 is 104
Please Enter Valid Input
Lowest Common Ancestor of 7 and 4 is-1
Lowest Common Ancestor of 5 and 8 is 101
Please Enter Valid Input
Lowest Common Ancestor of 5 and 10 is -1
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
// Node class
class Node{
public:
int val;
Node *left, *right;
Node(int Val){
val = Val;
left = nullptr;
right = nullptr;
}
};
bool b1, b2;
Node *findLCA(Node *node, int n1, int n2){
// Base case.
if (node == nullptr)
return nullptr;
Node *ans = nullptr;
if (node->val == n1){
b1 = true;
ans = node;
}
else if(node->val == n2){
b2 = true;
ans = node;
}
Node *leftAns = findLCA(node->left, n1, n2);
Node *rightAns = findLCA(node->right, n1, n2);
if (ans != nullptr)
return ans;
if (leftAns != nullptr && rightAns != nullptr)
return node;
return leftAns != nullptr ? leftAns : rightAns;
}
int LCA(Node *root, int n1, int n2) {
b1 = false;
b2 = false;
Node *lca = findLCA(root, n1, n2);
if(b1 && b2){
return lca->val;
}
cout << "Please enter valid input" << endl;
return -1;
}
int main() {
Node *root = new Node(1);
root->left = new Node(2);
root->left->left = new Node(4);
root->left->left->right = new Node(7);
root->left->right = new Node(5);
root->right = new Node(3);
root->right->right = new Node(6);
root->right->right->left = new Node(8);
root->right->right->right = new Node(9);
cout << "LCA of 4 and 5 is " <<
LCA (root, 4, 5) << endl;
cout << "LCA of 7 and 4 is " <<
LCA (root, 7, 4) << endl;
cout << "LCA of 5 and 8 is " <<
LCA (root, 5, 8) << endl;
cout << "LCA of 5 and 10 is " <<
LCA (root, 5, 10) << endl;
}
Output
LCA of 4 and 5 is 2
LCA of 7 and 4 is 4
LCA of 5 and 8 is 1
LCA of 5 and 10 is. Please enter valid input
-1
Python Implementation
# Node class
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
boolean = [False]*2
def findLCA(node, n1, n2):
if (node == None):
return None
answer = None
if (node.value == n1):
boolean[0] = True
answer = node
elif(node.value == n2):
boolean[1] = True
answer = node
leftAns = findLCA(node.left, n1, n2)
rightAns = findLCA(node.right, n1, n2)
if (answer != None):
return answer
if (leftAns != None and rightAns != None):
return node
if (leftAns != None):
return leftAns
else:
return rightAns
def LCA(root, n1, n2):
global boolean
boolean = [False, False]
lca = findLCA(root, n1, n2)
if(boolean[0] and boolean[1]):
return lca.value
print("Please enter valid input")
return -1
root = Node(3)
root.left = Node(8)
root.left.left = Node(9)
root.left.left.right = Node(10)
root.left.right = Node(12)
root.right = Node(32)
root.right.right = Node(63)
root.right.right.left = Node(89)
root.right.right.right = Node(93)
print("Lowest common Ancestor of 3 and 9 is ", LCA (root, 3, 9))
print("Lowest Common Ancestor of 10 and 12 is ", LCA (root, 10, 12))
print("Lowest common Ancestor of 32 and 89 is ", LCA (root, 32, 89))
print("Lowest common Ancestor of 63 and 93 is ", LCA (root, 63, 93))
Output
Lowest common Ancestor of 3 and 9 is 3
Lowest Common Ancestor of 10 and 12 is 8
Lowest common Ancestor of 32 and 89 is 32
Lowest common Ancestor of 63 and 93 is 63
Complexity Analysis
Let’s see the complexity of this approach.
Time Complexity: This approach’s Time Complexity will be O(n) to find the LCA of a binary tree. After traversing the whole binary tree in the worst case.
Space Complexity: The height of the recursive tree can reach up to O(h), where h is the height of the binary tree. The overall space complexity of this algorithm is O(h).
In this approach, we will find the lowest common ancestor using the iterative approach. The main idea is to traverse the binary tree until we have found both of our target nodes, and then we will traverse back from the target node to the root using the Map data structure in this example. Let’s see the steps of this approach.
Algorithm
Before moving forward, we must define the HashMap in which they store both keys and values.
You also have to declare a queue of node type that will be used to traverse the in-level order fashion.
Traverse in level order until we have found both our target nodes. While tracing, we will make sure that we map the nodes with their parents using the Map we declared initially.
In the next step, we must move from the target1 to the root node and store the pat in a HashSet data structure.
The first node is part of the part from target2 to the root node. This node is present in the HashSet in our answer
Java Implementation
import java.util.*;
class BinaryTree{
static int LowestCommonAncestor(Node root, int n1, int n2){
Map<Node,Node> parent = new HashMap<>() ;
Queue <Node> q = new LinkedList<>() ;
parent.put(root,null) ;
q.add(root) ;
Node x = null, y = null ;
while(!q.isEmpty() && (x == null || y == null)){
Node node = q.poll() ;
if(node.value == n1){
x = node ;
}else if(node.value == n2){
y = node ;
}
if(node.left != null){
parent.put(node.right,node) ;
q.add(node.right) ;
}
}
if(x == null || y== null)
return -1 ;
Set <Node> set = new HashSet<>();
while (x != null){
set.add(x) ;
x = parent.get(x) ;
}
while(!set.contains(y)){
set.add(y) ;
y = parent.get(y) ;
}
return y.value ;
}
public static void main(String args[]){
Node root = new Node(1) ;
root.left = new Node(2) ;
root.left.left = new Node(4) ;
root.left.left.right = new Node(8) ;
root.left.right = new Node(5) ;
root.right = new Node(10) ;
root.right.right = new Node(38) ;
root.right.right.left = new Node(10) ;
root.right.right.right = new Node(83) ;
System.out.println("Lowest common Ancestor 4 and 8 "+LowestCommonAncestor(root, 4, 8)) ;
System.out.println("Lowest common Ancestor 7 and 4 "+LowestCommonAncestor(root, 8, 9)) ;
System.out.println("Lowest common Ancestor 5 and 8 "+LowestCommonAncestor(root,5, 8));
System.out.println("Lowest common Ancestor 38 and 83"+LowestCommonAncestor(root,38,83)) ;
}
}
class Node{
int value ;
Node left, right ;
Node(int value){
this.value = value ;
}
}
Output
Lowest common Ancestor 4 and 8 -1
Lowest common Ancestor 7 and 4 -1
Lowest common Ancestor 5 and 8 -1
Lowest common Ancestor 38 and 83 -1
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
class Node{
public:
int val;
Node *left, *right;
Node(int Val){
val = Val;
left = nullptr;
right = nullptr;
}
};
int LCA(Node *root, int n1, int n2) {
unordered_map<Node*, Node*> parent;
queue<Node*> q;
parent[root]= nullptr;
q.push(root);
Node *x = nullptr, *y = nullptr;
while (!q.empty() && (x == nullptr || y == nullptr)){
Node *node = q.front();
q.pop();
if(node->val == n1){
x = node;
}
else if(node->val == n2){
y = node;
}
if(node->left != nullptr){
parent[node->left] = node;
q.push(node->left);
}
if(node->right != nullptr){
parent[node->right] = node;
q.push(node->right);
}
}
if (x == nullptr || y == nullptr)
return -1;
unordered_set<Node*> set;
while (x != nullptr){
set.insert(x);
x = parent[x];
}
while (set.find(y) == set.end()){
set.insert(y);
y = parent[y];
}
return y->val;
}
int main() {
Node *root = new Node(34);
root->left = new Node(33);
root->left->left = new Node(50);
root->left->left->right = new Node(60);
root->left->right = new Node(70);
root->right = new Node(80);
root->right->right = new Node(89);
root->right->right->left = new Node(92);
root->right->right->right = new Node(97);
cout << "Lowest common ancestor of 34 and 50 is " <<
LCA (root, 34, 50) << endl;
cout << "Lowest common ancestor of 60 and 80 is " <<
LCA (root, 60, 80) << endl;
cout << "Lowest common ancestor of 50 and 92 is " <<
LCA (root, 50, 92) << endl;
}
Output
Lowest common ancestor of 34 and 50 is 34
Lowest common ancestor of 60 and 80 is 34
Lowest common ancestor of 50 and 92 is 34
Python Implementation
# Node class
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def LCA(root, n1, n2):
parent = {}
q = []
parent[root] = None
q.append(root)
x, y = None, None
while (len(q) > 0 and (x == None or y == None)):
node = q.pop()
if(node.val == n1):
x = node
elif(node.val == n2):
y = node
if(node.left != None):
parent[node.left] = node
q.append(node.left)
if(node.right != None):
parent[node.right] = node
q.append(node.right)
if (x == None or y == None):
return -1
Set = set()
while (x != None):
Set.add(x)
x = parent[x]
while y not in Set:
Set.add(y)
y = parent[y]
return y.val
root = Node(5)
root.left = Node(23)
root.left.left = Node(45)
root.left.left.right = Node(78)
root.left.right = Node(80)
root.right = Node(85)
root.right.right = Node(90)
root.right.right.left = Node(93)
root.right.right.right = Node(100)
print("Lowest Common Ancestor of 5 and 23 is ", LCA (root, 5, 23))
print("Lowest Common Ancestor of 23 and 78 is ", LCA (root, 23, 78))
print("Lowest Common Ancestor of 45 and 90 is ", LCA (root, 45, 90))
Output
Lowest Common Ancestor of 5 and 23 is 5
Lowest Common Ancestor of 23 and 78 is 23
Lowest Common Ancestor of 45 and 90 is 5
Complexity Analysis
Let’s describe the time and space complexity of the lowest common ancestor.
Time Complexity: In this approach, we must traverse the whole tee in the worst case, which costs O(n) time. The overall time complexity required to find the lowest common ancestor of a binary tree is O(n).
Space Complexity: The space complexity of traversing a binary tree in a lever order fashion, the size queue can reach up to O(n). The overall space complexity is O(n).
Conclusion
This article taught us “how to find the lowest common ancestor in a Binary Tree.” We see various approaches to this problem. A common and efficient approach is one of the best approaches to solve this problem by recursive approach. By Understanding this approach, developers can make programs more efficient and useful. The recursive approach makes the program a balance of efficiency and simplicity, making the recursive approach a preferred choice for finding the lowest common Ancestor in binary trees.
FAQs
What is the Lowest Common Ancestor(LCA)?
The Lowest common ancestor of two nodes in the Binary tree is the deepest node, an ancestor of both nodes.
Can we find the Lowest Common Ancestor of more than two nodes?
Yes, Finding the Lowest Common Ancestor of more than two nodes can be extended from the binary case by iteratively applying the Lowest Common Ancestor function on pairs of nodes. This ensures the final result is the Lowest Common Ancestor of all the given nodes.
What is a Binary Tree?
A Binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left and right child. It is a special case of a tree data structure in which every node has either 0, 1, or 2 children.
Can the LCA be found iteratively in a Binary Tree?
It can be found iteratively, but it is more complex than the recursive approach. The iterative approach involves using parent pointers to trace the paths from the nodes to the root and then finding the intersection of these paths.
Deploying Applications Over the Cloud Using Jenkins
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
