Problem
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
Definition of LCA (according to Wikipedia): The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants.
For the given Binary tree, if info[key1] = 15 and info[key2] = 31, it should print: 21
Pseudocode
1. Traverse the given binary tree in an preorder fashion. 2. Do if info[root] == key1 or info[root] == key2, return root 3. Traverse root->left and root->right for key1 and key2 4. if key1 and key2, both are found 5. return (root). Since it is common to the path of both the keys key1 and key2; 6. end
Let the given tree be:
Code Implementation
//
// main.cpp
// Lowest Common Ancestor (LCA)
//
// Created by Himanshu on 31/10/21.
//
#include <iostream>
#include <queue>
using namespace std;
struct node {
int info = 0;
struct node *left, *right;
};
typedef struct node Node;
node* newNode(int data) {
node* Node = new node();
Node->info = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
Node* lca (Node *root, int n1, int n2) {
if (root == NULL) {
return NULL;
}
if (root->info == n1 || root->info == n2) {
return root;
}
Node *leftLCA = lca(root->left, n1, n2);
Node *rightLCA = lca(root->right, n1, n2);
if (leftLCA && rightLCA) {
return root;
}
return (leftLCA != NULL)? leftLCA : rightLCA;
}
int main() {
Node *root = newNode(1);
root->left = newNode(20);
root->right = newNode(21);
root->right->left = newNode(30);
root->right->right = newNode(31);
root->right->right->left = newNode(40);
root->right->right->left->right = newNode(51);
Node *key = NULL;
cout<<"The lowest common ancestors of 20 and 30 are: "<<endl;
key = lca(root, 20, 30);
cout<<(key->info);
cout<<endl;
cout<<"The lowest common ancestors of 40 and 51 are: "<<endl;
key = lca(root, 40, 51);
cout<<(key->info);
cout<<endl;
return 0;
}
Output
The lowest common ancestors of 20 and 30 are: 1 The lowest common ancestors of 40 and 51 are: 40
Time complexity of the above solution is O(n), where n is the number of nodes in tree. This is because it’s a simple tree traversal.
Here’s a working example: Lowest Common Ancestor