Lowest Common Ancestor in a Binary Tree
The lowest node in the tree that contains both n1 and n2 as descendants is the lowest common ancestor (LCA), and n1 and n2 are the nodes for which we are looking for the LCA. As a result, the common ancestor of nodes n1 and n2 that is placed the furthest from the root is the LCA of a binary tree containing nodes n1 and n2.
LCA in a Binary Tree Applications:
The distance from n1 to n2 can be calculated as the distance from the root to n1, plus the distance from the root to n2, minus twice the distance from the root to their lowest common ancestor, in order to determine the separation between pairs of nodes in a tree.
Methods to determine the LCA for n1 and n2 nodes.
Method 1 – Using the root to n1 and root to n2 paths
This method involves storing the path from the root to nodes n1 and n2 in different data structures. Then simultaneously search for the first difference among the values kept in the data structure.
Algorithm for the above method is:
- In a vector or in an array, store the path from the root node to n1 node.
- As above, consider another array or vector to store the path from root node to n2 node.
- Now, traverse both the arrays or vectors simultaneously till we reach the first mismatch node value.
- The node before the first mismatch node is the LCA (Lowest Common Ancestor)
Let’s look into the implementation of the above Method.
Java Implementation:
// A java program to find the Lowest Common Ancestor for n1 and n2 by the
// implementation of the above approach.
// This approach results an solution having O(1) time complexity.
import java.util.ArrayList;
import java.util.List;
// A Node structure for a binary tree.
class Node {
int val;
Node left, right;
Node (int value) {
val = value;
left = right = null;
}
}
public class BinaryTree_NoParentPtr
{
Node root;
private List <Integer> p1 = new ArrayList<> ();
private List <Integer> p2 = new ArrayList<> ();
// The below function helps in finding the path from the root node to the
// corresponding nodes n1 and n2.
int getLCA (int n1, int n2) {
p1.clear ();
p2.clear ();
return getLCAInternal (root, n1, n2);
}
private int getLCAInternal (Node root, int n1, int n2) {
if ( !getPath (root, n1, p1) || !getPath (root, n2, p2)) {
System.out.println ((p1. size () > 0) ? " The node n1 is present in the given tree. " : " The node n1 is missing in the given tree. ");
System.out.println ((p2. size () > 0) ? " The node n2 is present in the given tree " : " The node n2 is missing in the given tree. ");
return -1;
}
int i;
for (i = 0; i < p1.size () && i < p2.size (); i++) {
// System.out.println (p1.get (i) + " " + p2.get (i));
if (!p1.get (i).equals (p2.get (i)))
break;
}
return p1.get (i - 1);
}
// This method finds the path from the root node to the given node. Then it
// stores the complete path in a vector. If the path exists, this method will
// return true otherwise false.
private boolean getPath (Node root, int n, List <Integer> p)
{
// Checking if the given binary tree is NULL or not NULL.
if (root == null) {
return false;
}
// This method stores the node in the binary tree. It will be removed if the node // does not come into the path from root to node n.
path.add (root.val);
if (root.val == n) {
return true;
}
if (root.left != null && getPath (root.left, n, path)) {
return true;
}
if (root.right != null && getPath (root.right, n, path)) {
return true;
}
// This method will remove the root node from the path [] and return false
// if it is not present in subtree rooted with root.
path.remove (p.size ()-1);
return false;
}
// Driver program for the above functions.
public static void main (String [] args)
{
BinaryTree_NoParentPtr bt = new BinaryTree_NoParentPtr ();
bt. root = new Node (10);
bt. root. left = new Node (20);
bt. root. right = new Node (30);
bt. root. left. left = new Node (40);
bt. root. left. right = new Node (50);
bt. root. right. left = new Node (60);
bt. root. right. right = new Node (70);
System. out. println (" Lowest Common Ancestor (40, 50): " + bt.getLCA (40,50));
System. out. println (" Lowest Common Ancestor (40, 60): " + bt.getLCA (40,60));
System. out. println (" Lowest Common Ancestor (30, 40): " + bt.getLCA (30,40));
System. out. println (" Lowest Common Ancestor (20, 40): " + bt.getLCA (20,40));
}
}
OUTPUT:
Lowest Common Ancestor (40, 50) = 20
Lowest Common Ancestor (40, 60) = 10
Lowest Common Ancestor (30, 40) = 10
Lowest Common Ancestor (20, 40) = 20
Implementation of the above Method in C++ language:
// A C++ program to find the Lowest Common Ancestor for n1 and n2 by the
// implementation of the above approach.
// This method reflects a solution having O(1) Time complexity.
#include <iostream>
#include <vector>
using namespace std;
// A Node structure for the Binary Tree.
struct Node
{
int val;
struct Node *left, *right;
};
// The below utility function helps in creating a new binary tree node using the // given key value.
Node * newNode (int key)
{
Node *temp_node = new Node;
temp_node -> val = key;
temp_node -> left = temp_node -> right = NULL;
return temp_node;
}
// This method finds the path from the root node to the given node. Then it
// stores the complete path in a vector. If the path exists, this method will
// return true otherwise false.
bool getPath (Node *root, vector <int> &p, int k)
{
// Checking if the root node is NULL or not NULL.
if (root == NULL)
{
return false;
}
// This method stores the node in the binary tree. It will be removed if the node // does not come into the path from root to node n.
path. push_back (root -> val);
// Check if the given key is same as the root node’s value.
if (root -> val == k)
return true;
// Now check if the give key value if the data value of the left sub tree or the
// data value in the right sub tree.
if ((root -> left && getPath (root -> left, p, k)) ||
(root -> right && getPath (root->right, p, k)))
return true;
// If the given node is not present in the rooted sub tree, then it will be
// removed from the path.
path. pop_back ();
return false;
}
// This method will return the Lowest Common Ancestor, if nodes n1 and n2
// are present in the given binary tree.
// If the nodes n1 and n2 are not present in the given binary tree return -1.
int getLCA (Node *root, int n1, int n2)
{
// With the help of a vector, we store the path from the root node to node n1
// and path from the root node to node n2.
vector <int> p1, p2;
// Find paths from root node to node n1 and root node to node n2. This
// method checks for the presence of nodes n1 and n2. If either node n1 or
// node n2 is absent, it will return -1.
if (!getPath (root, p1, n1) || !getPath (root, p2, n2))
return -1;
/*
By considering the paths, it compares the nodes until it reaches the first differentiating node.
*/
int i;
for (i = 0; ( i < p1.size() && i < p2.size() ) ; i++)
if (p1 [i] != p2 [i])
break;
return p1 [i-1];
}
// Driver program code for testing the above functions.
int main ()
{
// Now we should create the binary tree by passing the node values into the // tree.
Node * root = newNode (10);
root -> left = newNode (20);
root -> right = newNode (30);
root -> left -> left = newNode (40);
root -> left -> right = newNode (50);
root -> right -> left = newNode (60);
root -> right -> right = newNode (70);
cout << "Lowest Common Ancestor (40, 50) = " << getLCA (root, 40, 50);
cout << "\n Lowest Common Ancestor (40, 60) = " << getLCA (root, 40, 60);
cout << "\n Lowest Common Ancestor (30, 40) = " << getLCA (root, 30, 40);
cout << "\n Lowest Common Ancestor (20, 40) = " << getLCA (root, 20, 40);
return 0;
}OUTPUT:
Lowest Common Ancestor (40, 50) = 20
Lowest Common Ancestor (40, 60) = 10
Lowest Common Ancestor (30, 40) = 10
Lowest Common Ancestor (20, 40) = 20
Implementation of the above Method in Python language:
# A Python program to find the Lowest Common Ancestor for n1 and n2 by
# the implementation of the above approach.
# This method reflects a solution having O(1) Time complexity.
# A node class for the binary tree.
class Node:
# The below constructor helps in creating a new node or the given binary
# tree.
def __init__(self, val):
self. val = val
self. left = None
self. right = None
# This method finds the path from the root node to the given node. Then it
# stores the complete path in a vector. If the path exists, this method will
# return true otherwise false.
def getPath (root, p, k):
# Checking If the given root node is NULL or not NULL.
if root is None:
return False
# If the given node is not present in the rooted sub tree, then it will be
# removed from the path.
path. append (root. val)
# Check if the given k value is same as the root node’s value.
if root. val == k:
return True
# Checking if the k value is present in the left sub tree or it is present in the right sub tree.
if ((root. left != None and getPath (root. left, p, k)) or
(root. right!= None and getPath (root. right, p, k))):
return True
# If the given node is not present in the rooted sub tree, then it will be
# removed from the path.
path. pop()
return False
# Returns the Lowest Common Ancestor, if both the nodes n1 and n2 are
# present in the given binary tree.
# If either of the nodes are not present in the given binary tree, the return -1.
def getLCA (root, n1, n2):
# Consider two arrays to store the paths from root node to node n1 and the
# path from root node to the node n2.
p1 = []
p2 = []
# Now, find the path from root node to node n1.
#Find the path from the root node to the node n2.
# Check if the nodes n1 and n2 are present. If either of them are not present, # then return -1.
if (not getPath (root, p1, n1) or not getPath (root, p2, n2)):
return -1
# To generate the first differentiating value, compare both the paths from the root node.
i = 0
while (i < len (p1) and i < len (p2)):
if p1[i] != p2[i]:
break
i += 1
return p1[i-1]
# Driver program code for testing the above functions.
# Now create a binary tree by inserting the given nodes in the provided order.
root = Node (10)
root. left = Node (20)
root. right = Node (30)
root. left. left = Node (40)
root. left. right = Node (50)
root. right. left = Node (60)
root. right. right = Node (70)
print (" Lowest Common Ancestor (40, 50) = %d " % (getLCA (root, 40, 50,)))
print (" Lowest Common Ancestor (40, 60) = %d " % (getLCA (root, 40, 60)))
print (" Lowest Common Ancestor (30, 40) = %d " % (getLCA (root, 30, 40)))
print (" Lowest Common Ancestor (20, 40) = %d " % (getLCA (root, 20, 40)))
OUTPUT:
Lowest Common Ancestor (40, 50) = 20
Lowest Common Ancestor (40, 60) = 10
Lowest Common Ancestor (30, 40) = 10
Lowest Common Ancestor (20, 40) = 20
Performance Analysis for the above approach.
The above approach requires a time complexity of O(n). As it stores both the paths in two different vectors and starts comparing from the root node.
It consumes a space of O(n) for the corresponding paths.
Note that the approach mentioned above relies on the existence of keys in the binary tree. It returns the current key as Lowest Common Ancestor if one key is present while the other is not (Ideally should have returned NULL). By first determining whether n1 and n2 are present in the tree and then determining their Lowest Common Ancestor, we can expand this approach to include all situations.
Method 2 – Using Single Traversal
We can find Lowest Common Ancestor with a single traversal of the Binary Tree and without extra storage for path arrays if we make an assumption that the keys n1 and n2 are present in the Binary Tree.
The plan is to work your way up the tree from the root. The root is Lowest Common Ancestor, if any of the given keys (either node n1 or node n2) matches the root (assuming that both keys are present). We repeat for the left and right subtrees if none of the keys match the root.
The Lowest Common Ancestor is the node that has one key in its left subtree and another key in its right subtree. Lowest Common Ancestor is also present in the left subtree if both keys are located there; otherwise, Lowest Common Ancestor is located in the right subtree.
We send the root to the helper function, which verifies to see if any of the node n1 or node n2 are found.
- If we found the node, then return the root node.
- Otherwise, call the left sub tree and right sub tree recursively.
In general, a preorder traversal is implemented. At first we check the data value, then recur through the left sub tree and as the final step we recur through the right sub tree.
If any case of a root node having only one child that is a NULL value and a not NULL value, the function will return the not NULL value.
A node which returns both not NULL values from the left and right sub trees, then that node is a Lowest common Ancestor node.
Let’s try to implement the above approach in java language.
//Java implementation to find lowest common ancestor of
// n1 and n2 using one traversal of binary tree
/* Class containing left and right child of current
node and key value*/
class Node
{
int data;
Node left, right;
public Node (int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree
{
//Root of the Binary Tree
Node root;
Node findLCA (int n1, int n2)
{
return findLCA (root, n1, n2);
}
// This function returns pointer to LCA of two given
// values n1 and n2. This function assumes that n1 and
// n2 are present in Binary Tree
Node findLCA (Node node, int n1, int n2)
{
// Base case
if (node == null)
return null;
// If either n1 or n2 matches with root's key, report
// the presence by returning root (Note that if a key is
// ancestor of other, then the ancestor key becomes LCA
if (node.data == n1 || node.data == n2)
return node;
// Look for keys in left and right subtrees
Node left_lca = findLCA (node.left, n1, n2);
Node right_lca = findLCA (node.right, n1, n2);
// If both of the above calls return Non - NULL, then one key
// is present in once subtree and other is present in other,
// So this node is the LCA
if (left_lca != null && right_lca != null)
return node;
// Otherwise check if left subtree or right subtree is LCA
return (left_lca != null) ? left_lca : right_lca;
}
/* Driver program to test above functions */
public static void main (String args[])
{
BinaryTree tree = new BinaryTree();
tree. root = new Node (10);
tree. root. left = new Node (20);
tree. root. right = new Node (30);
tree. root. left. left = new Node (40);
tree. root. left. right = new Node (50);
tree. root. right. left = new Node (60);
tree. root. right. right = new Node (70);
System. out. println (" LCA (40, 50) = " +
tree. findLCA (40, 50).data);
System. out. println (" LCA (40, 60) = " +
tree. findLCA (40, 60).data);
System. out. println (" LCA (30, 40) = " +
tree. findLCA (30, 40).data);
System. out. println (" LCA (20, 40) = " +
tree. findLCA (20, 40).data);
}
}
OUTPUT:
Lowest Common Ancestor (40, 50) = 20
Lowest Common Ancestor (40, 60) = 10
Lowest Common Ancestor (30, 40) = 10
Lowest Common Ancestor (20, 40) = 20