Finding LCA in a binary / multinode tree
Finding the LCA of node ‘A’ and node ‘B’ in a binary / multinode tree by hoping one level up and moving closer towards the other node
The idea behind this technique is to hop one level up from the node at greater depth upward till both the nodes become equal.
Algorithm : Finding LCA by hoping one level up and moving closer to the other node
- Use depth-first search to find the depth of each node and its parent in the tree.
- Get Lowest Common Ancestor (node_a, node_b)
- While node_a != node_b do :
- If depth of node_a > depth of node_b
- Swap node_a with node_b
- node_b = Get_Parent [ node_b ]
- node_a is the lowest common ancestor.
Consider the below example of finding lowest common ancestor of Node 10 & Node 13 in a multinode tree.
Data structure for storing tree : Adjacency List
Data structure for storing parent nodes : list / vector
Time complexity of finding LCA by hoping one level up and moving closer to other node : O(N).
Program for finding the lowest common ancestor (LCA) in a binary / multinode tree
#include<iostream>
#include<list>
#include<vector>
using namespace std;
class Tree{
private:
list<int> *adjlist;
vector<int> parentlist;
vector<bool> visited;
vector<int> depth;
public:
Tree() {
}
Tree (int nodes) {
adjlist = new list<int> [nodes+1];
parentlist.resize(nodes+1);
visited.resize(nodes+1);
depth.resize(nodes+1);
depth[0] = -1; // Hypothetical parent of root(1) is '0' at depth -1
}
~Tree() {
delete [] adjlist;
}
void AddEdge(int src, int dst) {
adjlist[src].push_back(dst);
adjlist[dst].push_back(src);
}
// Get parent of every node and find its depth
void GetParentAndDepth(int node, int parent) {
depth[node] = depth[parent] + 1;
for(auto& v : adjlist[node]) {
if (v != parent) {
parentlist[v] = node;
GetParentAndDepth(v, node);
}
}
}
// Consider node_b at greater depth. Move node_b a level closer to node_a which is higher up till both nodes become equal.
int GetLCA(int node_a, int node_b) {
while (node_a != node_b) {
if (depth[node_a] > depth[node_b]) {
swap(node_a, node_b);
}
node_b = parentlist[node_b];
}
return node_a;
}
};
int main(){
Tree t(20);
t.AddEdge(1, 2);
t.AddEdge(1, 3);
t.AddEdge(1, 4);
t.AddEdge(2, 5);
t.AddEdge(2, 6);
t.AddEdge(2, 7);
t.AddEdge(4, 8);
t.AddEdge(4, 9);
t.AddEdge(5, 10);
t.AddEdge(8, 12);
t.AddEdge(8, 19);
t.AddEdge(9, 16);
t.AddEdge(10, 11);
t.AddEdge(12, 13);
t.AddEdge(12, 14);
t.AddEdge(12, 15);
t.AddEdge(13, 20);
t.AddEdge(16, 17);
t.AddEdge(16, 18);
// Root node '1' does not have any parent; so set it to 0
t.GetParentAndDepth(1, 0);
cout << "LCA of (10, 13) : " << t.GetLCA(10, 13) << endl;
cout << "LCA of (7, 5) : " << t.GetLCA(7, 5) << endl;
cout << "LCA of (12, 9) : " << t.GetLCA(12, 9) << endl;
cout << "LCA of (19, 8) : " << t.GetLCA(19, 8) << endl;
cout << "LCA of (17, 18) : " << t.GetLCA(17, 18) << endl;
return 0;
}
Output
LCA of (10, 13) : 1
LCA of (7, 5) : 2
LCA of (12, 9) : 4
LCA of (19, 8) : 8
LCA of (17, 18) : 16
import java.util.ArrayList;
import java.util.List;
class Tree {
private List<List<Integer>> adjlist; // adjlist stores the tree in an adjacency list structure.
private List<Integer> parentlist; // parentlist stores the parent of every node
private List<Integer> depth; // depth stores the depth of every node. Root is at depth 0, parent of root is at level -1
Tree (int nodes) {
adjlist = new ArrayList<>(nodes+1);
parentlist = new ArrayList<>(nodes+1);
depth = new ArrayList<>(nodes+1);
for (int n=0; n<=nodes; n++) {
adjlist.add(new ArrayList<>());
depth.add(0); // Initailly add the depth of every node as 0. Update depth later.
parentlist.add(n); // Initially add every node as the parent of itself. Update parent later.
}
depth.set(0, -1); // Hypothetical parent of root(1) is '0' at depth -1
}
void AddEdge (int src, int dst) {
adjlist.get(src).add(dst);
adjlist.get(dst).add(src);
}
// Get the depth of every node and find its parent
void GetParentAndDepth (int node, int parent) {
depth.set(node, depth.get(parent)+1);
for (int v : adjlist.get(node)) {
if (v != parent) {
parentlist.set(v, node);
GetParentAndDepth(v, node);
}
}
}
// Consider node_b at greater depth. Move node_b a level closer to node_a which is higher up till both nodes become equal.
int GetLCA (int node_a, int node_b) {
while (node_a != node_b) {
if (depth.get(node_a) > depth.get(node_b)) {
int temp = node_a;
node_a = node_b;
node_b = temp;
}
node_b = parentlist.get(node_b);
}
return node_a;
}
public static void main(String args[]) {
Tree t = new Tree(20);
t.AddEdge(1, 2);
t.AddEdge(1, 3);
t.AddEdge(1, 4);
t.AddEdge(2, 5);
t.AddEdge(2, 6);
t.AddEdge(2, 7);
t.AddEdge(4, 8);
t.AddEdge(4, 9);
t.AddEdge(5, 10);
t.AddEdge(8, 12);
t.AddEdge(8, 19);
t.AddEdge(9, 16);
t.AddEdge(10, 11);
t.AddEdge(12, 13);
t.AddEdge(12, 14);
t.AddEdge(12, 15);
t.AddEdge(13, 20);
t.AddEdge(16, 17);
t.AddEdge(16, 18);
// Root node '1' does not have any parent; so set it to 0
t.GetParentAndDepth(1, 0);
System.out.println("LCA of (10, 13) : " + t.GetLCA(10, 13));
System.out.println("LCA of (7, 5) : " + t.GetLCA(7, 5));
System.out.println("LCA of (12, 9) : " + t.GetLCA(12, 9));
System.out.println("LCA of (19, 8) : " + t.GetLCA(19, 8));
System.out.println("LCA of (17, 18) : " + t.GetLCA(17, 18));
}
}
Output
LCA of (10, 13) : 1
LCA of (7, 5) : 2
LCA of (12, 9) : 4
LCA of (19, 8) : 8
LCA of (17, 18) : 16