Given the root of a binary tree and two nodes n1 and n2, find the LCA(Lowest Common Ancestor) of the nodes.
Table of Contents
Example
What is Lowest Common Ancestor(LCA)?
The ancestors of a node n are the nodes present in the path between root and node. Consider the binary tree shown in the example above.
Ancestors of 60 are 10, 30, 40 and 60
Ancestors of 50 are 10, 30 and 50
The lowest common ancestor of n1 and n2 is the lowermost(in the binary tree) common ancestor of two nodes or the last common ancestor of the two nodes. That is, for 50 and 60 the LCA is 30.
Naive Approach for Lowest Common Ancestor
LCA of n1 and n2 can be found as,
- Find and store the path from the root to n1 in an array path1.
- Find and store the path from the root to n2 in another array path2.
- If there is no path from the root to n1(root n1 does not exist) or from root to n2(root n2 does not exist) return null.
- Else compare the two path arrays, LCA is the last common node in the path arrays.
Find Path Algorithm
If a path from the root to the given node exists, store the path in an array and return true else return false.
- If the root is null return false.
- Add the current node in the path array, if the current node is the required node return true.
- Check for path in the left and right subtree by recursively calling the findPath function for the left and right subtree.
- If there exists a path in either left or right subtree, return true.
- Else remove the current node from the path array and return false.
JAVA Code for Lowest Common Ancestor
import java.util.*;
public class BinaryTreeLCA {
// class to represent node of a binary tree
static class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
private static Node LCA(Node root, int n1, int n2) {
// Stores path from root to n1
ArrayList<Node> path1 = new ArrayList<>();
// Stores path from root to n2
ArrayList<Node> path2 = new ArrayList<>();
if (!findPath(root, n1, path1) || !findPath(root, n2, path2)) {
// Either n1 or n2 does not exists in the tree
return null;
}
// Compare the two path arrays
Node LCA = null;
for (int i = 0; i < path1.size() && i < path2.size(); i++) {
if (path1.get(i) != path2.get(i)) {
// First non common node
break;
} else {
LCA = path1.get(i);
}
}
return LCA;
}
// Function to find the path from root to given node and store it in an array
private static boolean findPath(Node root, int n, ArrayList<Node> path) {
if (root == null) {
// Return false if root is null
return false;
}
// Add the current root in the path array
path.add(root);
// If this node is the required node return true
if (root.data == n) {
return true;
}
// Find path in the left and right sub tree
if (findPath(root.left, n, path) || findPath(root.right, n, path)) {
// If there is a path in either left or right sub tree return true
return true;
}
// Else remove root from path array and return false
path.remove(root);
return false;
}
public static void main(String[] args) {
// Construct the tree shown in above example
Node root = new Node(10);
root.left = new Node(20);
root.right = new Node(30);
root.right.left = new Node(40);
root.right.right = new Node(50);
root.right.left.left = new Node(60);
root.right.right.left = new Node(70);
root.right.right.right = new Node(80);
// Queries
System.out.println(LCA(root, 20, 80).data);
System.out.println(LCA(root, 80, 30).data);
System.out.println(LCA(root, 70, 80).data);
}
}C++ Code for Lowest Common Ancestor
#include <iostream>
#include <vector>
using namespace std;
// Class representing node of binary tree
class Node {
public:
int data;
Node *left;
Node *right;
};
// Function to allocate new memory to a tree node
Node* newNode(int data) {
Node *node = new Node();
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
// Function to find the path from root to given node and store it in an array
bool findPath(Node *root, int n, vector<int> &path) {
if (root == NULL) {
// Return false if root is null
return false;
}
// Add the current root in the path array
path.push_back(root->data);
// If this node is the required node return true
if (root->data == n) {
return true;
}
// Find path in the left and right sub tree
if (findPath(root->left, n, path) || findPath(root->right, n, path)) {
// If there is a path in either left or right sub tree return true
return true;
}
// Else remove root from path array and return false
path.pop_back();
return false;
}
int LCA(Node *root, int n1, int n2) {
// Stores path from root to n1
vector<int> path1;
// Stores path from root to n2
vector<int> path2;
if (!findPath(root, n1, path1) || !findPath(root, n2, path2)) {
// Either n1 or n2 does not exists in the tree
return -1;
}
// Compare the two path arrays
int i = 0;
for (; i < path1.size() && i < path2.size(); i++) {
if (path1[i] != path2[i]) {
// First non common node
break;
}
}
return path1[i - 1];
}
int main() {
// Construct the tree shown in above example
Node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->right->left = newNode(40);
root->right->right = newNode(50);
root->right->left->left = newNode(60);
root->right->right->left = newNode(70);
root->right->right->right = newNode(80);
// Queries
cout<<LCA(root, 20, 80)<<endl;
cout<<LCA(root, 80, 30)<<endl;
cout<<LCA(root, 70, 80)<<endl;
return 0;
}10 30 50
Complexity Analysis
Time Complexity = O(n)
The above solution requires 3 traversals of the tree, two to fill the path arrays, and 1 to compare these arrays.
Optimized Approach for Lowest Common Ancestor
If we assume that n1 and n2, for which we have to find LCA, exists in the tree, then the above problem can be solved in a single traversal.
Traverse the tree, for every node we have one of the four cases,
- The current node is either n1 or n2, in this case, we return the node.
- One of the subtrees of the current node contains n1 and the other contains n2, this node is the LCA, return the node.
- One subtree of the current node contains both n1 and n2, we return what the subtree returns.
- None of the subtrees contains n1 and n2, return null.
JAVA Code for Lowest Common Ancestor
import java.util.ArrayList;
public class Naive {
// class to represent node of a binary tree
static class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
private static Node LCA(Node root, int n1, int n2) {
// Stores path from root to n1
ArrayList<Node> path1 = new ArrayList<>();
// Stores path from root to n2
ArrayList<Node> path2 = new ArrayList<>();
if (!findPath(root, n1, path1) || !findPath(root, n2, path2)) {
// Either n1 or n2 does not exists in the tree
return null;
}
// Compare the two path arrays
Node LCA = null;
for (int i = 0; i < path1.size() && i < path2.size(); i++) {
if (path1.get(i) != path2.get(i)) {
// First non common node
break;
} else {
LCA = path1.get(i);
}
}
return LCA;
}
// Function to find the path from root to given node and store it in an array
private static boolean findPath(Node root, int n, ArrayList<Node> path) {
if (root == null) {
// Return false if root is null
return false;
}
// Add the current root in the path array
path.add(root);
// If this node is the required node return true
if (root.data == n) {
return true;
}
// Find path in the left and right sub tree
if (findPath(root.left, n, path) || findPath(root.right, n, path)) {
// If there is a path in either left or right sub tree return true
return true;
}
// Else remove root from path array and return false
path.remove(root);
return false;
}
public static void main(String[] args) {
// Construct the tree shown in above example
Node root = new Node(10);
root.left = new Node(20);
root.right = new Node(30);
root.right.left = new Node(40);
root.right.right = new Node(50);
root.right.left.left = new Node(60);
root.right.right.left = new Node(70);
root.right.right.right = new Node(80);
// Queries
System.out.println(LCA(root, 20, 80).data);
System.out.println(LCA(root, 80, 30).data);
System.out.println(LCA(root, 70, 80).data);
}
}C++ Code for Lowest Common Ancestor
#include <iostream>
#include <vector>
using namespace std;
// Class representing node of binary tree
class Node {
public:
int data;
Node *left;
Node *right;
};
// Function to allocate new memory to a tree node
Node* newNode(int data) {
Node *node = new Node();
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
Node* LCA(Node *root, int n1, int n2) {
// Return null for a null root
if (root == NULL) {
return NULL;
}
// Current node is either n1 or n2
if (root->data == n1 || root->data == n2) {
return root;
}
// Traverse the tree to find the LCA in left and right sub tree
Node *LCA1 = LCA(root->left, n1, n2);
Node *LCA2 = LCA(root->right, n1, n2);
// One of the sub tree contains n1 and other contains n2, this is the LCA
if (LCA1 != NULL && LCA2 != NULL) {
return root;
}
// Left sub tree contains both n1 and n2, return what sub tree returns
if (LCA1 != NULL) {
return LCA1;
}
// Right sub tree contains both n1 and n2, return what sub tree returns
if (LCA2 != NULL) {
return LCA2;
}
// None of the sub tree contains n1 and n2
return NULL;
}
int main() {
// Construct the tree shown in above example
Node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->right->left = newNode(40);
root->right->right = newNode(50);
root->right->left->left = newNode(60);
root->right->right->left = newNode(70);
root->right->right->right = newNode(80);
// Queries
cout<<LCA(root, 20, 80)->data<<endl;
cout<<LCA(root, 80, 30)->data<<endl;
cout<<LCA(root, 70, 80)->data<<endl;
return 0;
}10 30 50
Complexity Analysis
Time Complexity = O(n) where n is the number of nodes present in the given tree.
The above solution requires a single traversal to find the LCA.