Problem Statement
Given a binary tree, and two values v1 and v2, find the lowest common ancestor of nodes with their values as v1 and v2.
Where the lowest common ancestor of two nodes (Node1 and Node2) is the deepest node of which Node1 and Node2 are descendants. Note that here we consider that a node is the descendant of itself also.
Examples
Example 1 –
Input – Given Tree –
1
/ \
/ \
2 3
/ \ \
/ \ \
4 5 6
\ / \
\ / \
7 8 9
LCA Queries –
- LCA (4, 5)
- LCA (7, 4)
- LCA (5, 8)
Output –
LCA of 4 and 5 is 2
LCA of 7 and 4 is 4
LCA of 5 and 8 is 1
Explanation – By seeing the tree structure we can see that –
- 2 is the deepest node in the tree whose descendant nodes are 4 and 5.
- 4 is the deepest node in the tree whose descendant nodes are 7 and 4.
- 1 is the deepest node in the tree whose descendant nodes are 5 and 8.
Example 2 –
Input – Given Tree –
1
|
|
2
|
|
3
/ \
/ \
4 5
LCA Queries –
- LCA (4, 2)
- LCA (4, 5)
Output –
LCA of 4 and 2 is 2
LCA of 4 and 5 is 3
Explanation – By seeing the tree structure we can see that –
- 2 is the deepest node in the tree whose descendant nodes are 4 and 2.
- 3 is the deepest node in the tree whose descendant nodes are 4 and 5.
Constraints
- 0<n<105, where n is the number of nodes.
- 0<node.val<109
Approach 1: By Storing Root To n1 And Root To n2 Paths
In any tree structure there exists a unique path between any two nodes. Therefore there must exist a unique path from the root to node n1 and n2. Also, there will be some common nodes in both paths because we are starting from the root node.
Algorithm
To find the lowest common ancestor of a binary tree we will perform the following steps –
- Store the path from the root to n1 in a list, let it be path1.
- Store the path from the root to n2 in a list, let it be path2.
- Traverse in both the obtained paths till nodes are common and return the node that occurs just before the mismatch.
Now let’s see how we can find the path from the root to the target –
- Define an empty list of integers (say path) and pass it to a boolean type recursive function findPath that accepts three arguments i.e.i.e. root, val, and path.
- If the root is null then return false.
- Push root.val in the path list.
- Now, if root.val is equal to val then return true as we’ve found the desired node.
- Then if on recurring on the left and right subtree we find our desired node in any of the subtree return true.
- Now to backtrack, remove the element at the last position in our path list.
- At last, if nothing worked out then return false.
Dry Run
Let’s dry run this approach to find the LCA of a binary tree shown below – Given Tree –
1
/ \
/ \
2 3
/ \ \
/ \ \
4 5 6
\ / \
\ / \
7 8 9
- Query 1 – LCA (4, 5)
- Find the path from the root node to the node with value 4. path1 = [1→2→4]
- Find the path from the root node to the node with value 5. path2 = [1→2→5]
- Now, we traverse both the lists till the path is the same (the value of nodes in the path is the same in both lists). Therefore at the 2nd index (0-based), we found a mismatch, and hence we will return the value just before the 2nd index i.e.i.e. 2.
- Query 2 – LCA (7, 4)
- Find the path from the root node to the node with value 7. path1 = [1→2→4→7]
- Find the path from the root node to node with value 4. path2 = [1→2→4]
- Now, we traverse in both the lists till the path is same (value of nodes in the path is same). Here, we will reach the last index of path1 and do not find any mismatch therefore we will return the node at the last index of path1.
- Query 3 – LCA (5, 8)
- Find the path from the root node to the node with value 5. path1 = [1→2→4]
- Find the path from the root node to the node with value 8. path2 = [1→3→7→8]
- Now, we traverse in both the lists till the path is the same (value of nodes in the path is the same). At the 1st index, we encounter a mismatch in paths so we will return the node present at the 0th index i.e.i.e. 1.
Java Implementation
import java.util.*;
public class Main{
// Node class
static class Node{
int val;
Node left, right;
Node(int val){
this.val=val;
}
}
// Function to find the path from the root node
// to the target node.
static boolean findPath (Node root, int val,
List<Integer> path){
// Returnig false if we encounter a null node.
if (root == null)
return false;
path.add(root.val);
// Returning true, if we encounter the
// target node.
if(root.val == val){
return true;
}
// Returning true if we find the
// target node in any of the subtree.
if(findPath(root.left, val, path)
|| findPath(root.right, val, path)){
return true;
}
// Backtrack by removing the last element
// of the path list.
path.remove(path.size() - 1);
// Returning false if nothing worked out.
return false;
}
// Helper function to find the LCA
static int findLCA(Node root, int n1, int n2){
// Using a function to find the path from
// root to n1 or n2.
if (!findPath(root, n1, path1)
|| !findPath(root, n2, path2)){
System.out.println("Please enter valid input");
return -1;
}
int ind;
// Now iterate over the path list found.
for (ind = 0; ind < path1.size()
&& ind < path2.size(); ind++){
// If there is a mismatch break the loop.
if(path1.get(ind) != path2.get(ind))
break;
}
// Return the node encountered just before
// the mismatch.
return path1.get(ind - 1);
}
// Function to find the LCA
static int LCA(Node root, int n1, int n2) {
path1 = new ArrayList<>();
path2 = new ArrayList<>();
return findLCA(root, n1, n2);
}
// Lists to store the path
static List<Integer> path1;
static List<Integer> path2;
public static void main(String[] args) {
// Making the following tree
// 1
// / \
// / \
// 2 3
// / \ \
// / \ \
// 4 5 6
// \ / \
// \ / \
// 7 8 9
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);
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));
// Passing the wrong input
System.out.println("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
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;
}
};
// Lists to store the path
vector<int> path1;
vector<int> path2;
// Function to find the path from the root node
// to the target node.
bool findPath (Node *root, int val,
vector<int> &path){
// Returnig false if we encounter a nullptr node.
if (root == nullptr)
return false;
path.push_back(root->val);
// Returning true, if we encounter the
// target node.
if(root->val == val){
return true;
}
// Returning true if we find the
// target node in any of the subtree.
if(findPath(root->left, val, path)
|| findPath(root->right, val, path)){
return true;
}
// Backtrack by removing the last element
// of the path list.
path.pop_back();
// Returning false if nothing worked out.
return false;
}
// Helper function to find the LCA
int findLCA(Node *root, int n1, int n2){
// Using a function to find the path from
// root to n1 or n2.
if (!findPath(root, n1, path1)
|| !findPath(root, n2, path2)){
cout << "Please enter valid input" << endl;
return -1;
}
int ind;
// Now iterate over the path list found.
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 the node encountered just before
// the mismatch.
return path1[ind - 1];
}
// Function to find the LCA
static int LCA(Node *root, int n1, int n2) {
path1.clear();
path2.clear();
return findLCA(root, n1, n2);
}
int main() {
// Making the following tree
// 1
// / \
// / \
// 2 3
// / \ \
// / \ \
// 4 5 6
// \ / \
// \ / \
// 7 8 9
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;
// Passing the wrong input
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
Please enter valid input
LCA of 5 and 10 is -1
Python
# Node class
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# Lists to store the path
path1 = []
path2 = []
# Function to find the path from the root node
# to the target node.
def findPath (root, val, path):
# Returnig false if we encounter a nullptr node.
if (root == None):
return False
path.append(root.val)
# Returning true, if we encounter the
# target node.
if(root.val == val):
return True
# Returning true if we find the
# target node in any of the subtree.
if(findPath(root.left, val, path)
or findPath(root.right, val, path)):
return True
# Backtrack by removing the last element
# of the path list.
path.pop()
# Returning false if nothing worked out.
return False
# Helper function to find the LCA
def findLCA(root, n1, n2):
# Using a function to find the path from
# root to n1 or n2.
if (findPath(root, n1, path1) == False
or findPath(root, n2, path2) == False):
print("Please enter valid input")
return -1
ind = 0
# Now iterate over the path list found.
while( ind < len(path1) and ind < len(path2)):
# If there is a mismatch break the loop.
if(path1[ind] != path2[ind]):
break
ind+=1
# Return the node encountered just before
# the mismatch.
return path1[ind - 1]
# Function to find the LCA
def LCA(root, n1, n2):
global path1, path2
path1 = []
path2 = []
return findLCA(root, n1, n2)
# Driver code
# Making the following tree
# 1
# / \
# / \
# 2 3
# / \ \
# / \ \
# 4 5 6
# \ / \
# \ / \
# 7 8 9
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))
# Passing the wrong input
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 – To get root to target path we need to traverse the whole binary tree, which costs O(n) time, where n is the number of nodes present in the tree. Therefore, it requires O(n) time to find LCA of a binary tree.
- Space Complexity – The height of the recursive tree can reach up to O(h), also in the worst case (target node is the deepest leaf), the size of the path list will be O(h) where h is the height of the binary tree. Hence, the overall space complexity is O(h).
Approach 2 – Using Single Traversal (Recursive Approach)
In the previous approach, it requires traversing the tree two times (once to find the path from the root node to 1st1st target node and from the root node to the 2nd2nd target node). But we can optimize our approach such that it requires only a single traversal to find the lowest common ancestor of a binary tree.
The idea is to traverse the tree starting from the root. If the node’s value does not match with any of the target key i.e.i.e. n1 or n2 we recur for both the left and the right subtree. Else if the left subtree contains one key and the right subtree contains one key then the node is the LCA of a binary tree. Otherwise, if the left subtree contains both the keys then LCA is present in the left sub-tree, else it is present in the right subtree.
Algorithm
The steps required in the algorithm to find LCA of a binary tree as follows –
- Define two boolean values (say b1 and b2) which will help us to verify that both keys provided as the input exists in a binary tree or not.
- Define a Node type recursive function findLCA that accepts three arguments i.e.i.e. node, n1, and n2.
- Define a base condition that returns null whenever the node is null.
- Define a variable ans and initialize it to be null.
- Check if node.val is equal to n1, make b1 to be true, and assign the node to ans.
- Otherwise, check if node.val is equal to n2, make b2 to be true, and assign the node to ans.
- Now, recurse for the left and the right subtree and store their return value in variables (say leftAns and rightAns).
- If we have found that ans is no longer equal to null then we will return it.
- Otherwise, if we found that both the leftAns and rightAns are not null then we will return the node.
- At last, we will check if leftAns is not null then we will return leftAns otherwise we will return rightAns.
- Now we will check if both the values b1 and b2 are true or not. If they both are true we will return the value of the node returned by the recursive function. Otherwise, we will return -1.
Java Implementation
import java.util.*;
public class Main{
// Node class
static class Node{
int val;
Node left, right;
Node(int val){
this.val=val;
}
}
// boolean variables (required to check if the node
// with target value exists in the tree.)
static boolean b1, b2;
// Helper function to find the LCA
static Node findLCA(Node node, int n1, int n2){
// Base case.
if (node == null)
return null;
// Declare a variable to store the answer.
Node ans = null;
// If the node's value matches with n1.
if (node.val == n1){
// Make b1 to be true, as we've found
// target 1.
b1 = true;
ans = node;
}
// Otherwsie, check if the node's value
// matches with n2.
else if(node.val == n2){
// Make b2 to be true, as we've found
// target 2.
b2 = true;
ans = node;
}
// Check for the target nodes in the left
// and the right subtree.
Node leftAns = findLCA(node.left, n1, n2);
Node rightAns = findLCA(node.right, n1, n2);
// Check if we have modified the answer value
if (ans != null)
return ans;
// If one of the target node lies in the left subtree
// and another lies in the right subtree.
if (leftAns != null && rightAns !=null)
return node;
// Otherwise, one node must lie in left subtree
// and another in right subtree. (If target exists in tree).
return leftAns != null ? leftAns : rightAns;
}
// Function to find the LCA
static int LCA(Node root, int n1, int n2) {
// Initialize b1 and b2 to be false.
b1 = false;
b2 = false;
// Store the potential LCA candidate.
Node lca = findLCA(root, n1, n2);
// If both n1 and n2 exists in the tree.
if(b1 && b2){
return lca.val;
}
System.out.println("Please enter valid input");
return -1;
}
public static void main(String[] args) {
// Making the following tree
// 1
// / \
// / \
// 2 3
// / \ \
// / \ \
// 4 5 6
// \ / \
// \ / \
// 7 8 9
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);
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));
// Passing the wrong input
System.out.println("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
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;
}
};
// boolean variables (required to check if the node
// with target value exists in the tree.)
bool b1, b2;
// Helper function to find the LCA
Node *findLCA(Node *node, int n1, int n2){
// Base case.
if (node == nullptr)
return nullptr;
// Declare a variable to store the answer.
Node *ans = nullptr;
// If the node's value matches with n1.
if (node->val == n1){
// Make b1 to be true, as we've found
// target 1.
b1 = true;
ans = node;
}
// Otherwsie, check if the node's value
// matches with n2.
else if(node->val == n2){
// Make b2 to be true, as we've found
// target 2.
b2 = true;
ans = node;
}
// Check for the target nodes in the left
// and the right subtree.
Node *leftAns = findLCA(node->left, n1, n2);
Node *rightAns = findLCA(node->right, n1, n2);
// Check if we have modified the answer value
if (ans != nullptr)
return ans;
// If one of the target node lies in the left subtree
// and another lies in the right subtree.
if (leftAns != nullptr && rightAns != nullptr)
return node;
// Otherwise, one node must lie in left subtree
// and another in right subtree. (If target exists in tree).
return leftAns != nullptr ? leftAns : rightAns;
}
// Function to find the LCA
int LCA(Node *root, int n1, int n2) {
// Initialize b1 and b2 to be false.
b1 = false;
b2 = false;
// Store the potential LCA candidate.
Node *lca = findLCA(root, n1, n2);
// If both n1 and n2 exists in the tree.
if(b1 && b2){
return lca->val;
}
cout << "Please enter valid input" << endl;
return -1;
}
int main() {
// Making the following tree
// 1
// / \
// / \
// 2 3
// / \ \
// / \ \
// 4 5 6
// \ / \
// \ / \
// 7 8 9
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;
// Passing the wrong input
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
Please enter valid input
LCA of 5 and 10 is -1
Python Implementation
# Node class
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# boolean variables (required to check if the node
# with target value exists in the tree.)
boolean = [False]*2
# Helper function to find the LCA
def findLCA(node, n1, n2):
# Base case.
if (node == None):
return None
# Declare an variable to store the answer.
ans = None
# If the node's value matches with n1.
if (node.val == n1):
# Make boolean[1] to be true, as we've found
# target 1.
boolean[0] = True
ans = node
# Otherwsie, check if the node's value
# matches with n2.
elif(node.val == n2):
# Make boolean[2] to be true, as we've found
# target 2.
boolean[1] = True
ans = node
# Check for the target nodes in the left
# and the right subtree.
leftAns = findLCA(node.left, n1, n2)
rightAns = findLCA(node.right, n1, n2)
# Check if we have modified the answer value
if (ans != None):
return ans
# If one of the target node lies in the left subtree
# and another lies in the right subtree.
if (leftAns != None and rightAns != None):
return node
# Otherwise, one node must lie in left subtree
# and another in right subtree. (If target exists in tree).
if (leftAns != None):
return leftAns
else:
return rightAns
# Function to find the LCA
def LCA(root, n1, n2):
# Initialize boolean list.
global boolean
boolean = [False, False]
# Store the potential LCA candidate.
lca = findLCA(root, n1, n2)
# If both n1 and n2 exists in the tree.
if(boolean[0] and boolean[1]):
return lca.val
print("Please enter valid input")
return -1
# Driver code
# Making the following tree
# 1
# / \
# / \
# 2 3
# / \ \
# / \ \
# 4 5 6
# \ / \
# \ / \
# 7 8 9
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))
# Passing the wrong input
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 – Since we will be traversing the whole binary tree in the worst case. Therefore, it requires O(n) time to find LCA of a binary tree.
- Space Complexity – The height of the recursive tree can reach up to O(h), where h is the height of the binary tree. Hence, the overall space complexity is O(h).
Approach 3 – Iterative Approach
In our last approach, we’ve seen how we can store the paths from the root node to the target nodes and use them to find the lowest common ancestor. Here, we will see how we can find the lowest common ancestor of the binary tree using an iterative method. The main idea is to traverse the tree until we have found both of our target nodes and then we will traverse back from the target node to the root node using the Map data structure.
Let’s see the steps involved in the algorithm –
- Define a HashMap in which both the key and value are of the node type.
- Also declare a Queue of Node type which will be used to traverse the in level-order fashion.
- Then traverse in level order till we haven’t found both of our target nodes. Also, while traversing we will make sure that we map the nodes with their parents using the Map we declared initially.
- Now we will move from target1 to the root node and store the path in a HashSet.
- Then, we will move from target2 to the root node until the nodes in the path are not present in the HashSet.
- The very first node that is part of the path from target2 to the root node and is present in the HashSet is our answer.
Java Implementation
import java.util.*;
public class Main{
// Node class
static class Node{
int val;
Node left, right;
Node(int val){
this.val=val;
}
}
// Function to find the LCA
static int LCA(Node root, int n1, int n2) {
// Declaring the hashmap to keep track of
// the parents.
Map<Node, Node> parent = new HashMap<>();
// Declaring the q to traverse the tree.
Queue<Node> q = new LinkedList<>();
// Parent of the root is null.
parent.put(root, null);
q.add(root);
// x will hold the address of node with
// value n1 and y will hold the node
// with value n2 (if exists).
Node x = null, y = null;
// Iterating while there are more nodes to explore
// in the tree and we haven't found both of our
// target nodes.
while (!q.isEmpty() && (x == null || y == null)){
// Polling (Removing) node from the queue.
Node node = q.poll();
// If node's value is n1.
if(node.val == n1){
x = node;
}
// If node's value is n2.
else if(node.val == n2){
y = node;
}
// If there is subtree in node's left.
if(node.left != null){
parent.put(node.left, node);
q.add(node.left);
}
// If there is subtree in node's right.
if(node.right != null){
parent.put(node.right, node);
q.add(node.right);
}
}
// If anyone of the node is null, then
// no LCA exists.
if (x == null || y == null)
return -1;
// Defining the set.
Set<Node> set = new HashSet<>();
// Iterating while x is not null and storing
// path from x to the root node.
while (x != null){
set.add(x);
x = parent.get(x);
}
// Iterating while nodes in the path from y to
// the root are different.
while (!set.contains(y)){
set.add(y);
y = parent.get(y);
}
// Return y.val
return y.val;
}
public static void main(String[] args) {
// Making the following tree
// 1
// / \
// / \
// 2 3
// / \ \
// / \ \
// 4 5 6
// \ / \
// \ / \
// 7 8 9
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);
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));
// Passing the wrong input
System.out.println("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
LCA 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;
}
};
// Function to find the LCA
int LCA(Node *root, int n1, int n2) {
// Declaring the hashmap to keep track of
// the parents.
unordered_map<Node*, Node*> parent;
// Declaring the q to traverse the tree.
queue<Node*> q;
// Parent of the root is nullptr.
parent[root]= nullptr;
q.push(root);
// x will hold the address of node with
// value n1 and y will hold the node
// with value n2 (if exists).
Node *x = nullptr, *y = nullptr;
// Iterating while there are more nodes to explore
// in the tree and we haven't found both of our
// target nodes.
while (!q.empty() && (x == nullptr || y == nullptr)){
// Polling (Removing) node from the queue.
Node *node = q.front();
q.pop();
// If node's value is n1.
if(node->val == n1){
x = node;
}
// If node's value is n2.
else if(node->val == n2){
y = node;
}
// If there is subtree in node's left.
if(node->left != nullptr){
parent[node->left] = node;
q.push(node->left);
}
// If there is subtree in node's right.
if(node->right != nullptr){
parent[node->right] = node;
q.push(node->right);
}
}
// If anyone of the node is nullptr, then
// no LCA exists.
if (x == nullptr || y == nullptr)
return -1;
// Defining the set.
unordered_set<Node*> set;
// Iterating while x is not nullptr and storing
// path from x to the root node.
while (x != nullptr){
set.insert(x);
x = parent[x];
}
// Iterating while nodes in the path from y to
// the root are different.
while (set.find(y) == set.end()){
set.insert(y);
y = parent[y];
}
// Return y.val
return y->val;
}
int main() {
// Making the following tree
// 1
// / \
// / \
// 2 3
// / \ \
// / \ \
// 4 5 6
// \ / \
// \ / \
// 7 8 9
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;
// Passing the wrong input
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
Please enter valid input
LCA of 5 and 10 is -1
Python Implementation
# Node class
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# Function to find the LCA
def LCA(root, n1, n2):
# Declaring the hashmap to keep track of
# the parents.
parent = {}
# Declaring the q to traverse the tree.
q = []
# Parent of the root is null.
parent[root] = None
q.append(root)
# x will hold the address of node with
# value n1 and y will hold the node
# with value n2 (if exists).
x, y = None, None
# Iterating while there are more nodes to explore
# in the tree and we haven't found both of our
# target nodes.
while (len(q) > 0 and (x == None or y == None)):
# Polling (Removing) node from the queue.
node = q.pop()
# If node's value is n1.
if(node.val == n1):
x = node
# If node's value is n2.
elif(node.val == n2):
y = node
# If there is subtree in node's left.
if(node.left != None):
parent[node.left] = node
q.append(node.left)
# If there is subtree in node's right.
if(node.right != None):
parent[node.right] = node
q.append(node.right)
# If anyone of the node is null, then
# no LCA exists.
if (x == None or y == None):
return -1
# Defining the set.
Set = set()
# Iterating while x is not null and storing
# path from x to the root node.
while (x != None):
Set.add(x)
x = parent[x]
# Iterating while nodes in the path from y to
# the root are different.
while y not in Set:
Set.add(y)
y = parent[y]
# Return y.val
return y.val
# Driver code
# Making the following tree
# 1
# / \
# / \
# 2 3
# / \ \
# / \ \
# 4 5 6
# \ / \
# \ / \
# 7 8 9
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))
# Passing the wrong input
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
LCA of 5 and 10 is -1
Complexity Analysis
Time Complexity – We need to traverse the whole tree in the worst case which costs O(n) time. Hence, the overall time complexity to find LCA of a binary tree is O(n). Space Complexity – To traverse the binary tree in a level order fashion, the size of the queue can reach up to O(n). Hence, the overall space complexity is O(n).
Conclusion
- The lowest common ancestor (LCA) of two nodes in a binary tree is the deepest node which is the ancestor of both the nodes.
- Lowest common ancestor can be found by storing paths from the root node to the target nodes and the finding the last common node in the path. Which requires O(n) time.
- LCA can easily be found by traversing the binary tree once, and finding the positions of the target nodes. Which again requires O(n) time, but only a single traversal of tree is needed.
- It is very much used practically also, for example, to find the directory inside which two or more given directories are present.
