Lowest common ancestor (LCA) in a Binary tree in C++

By Zeeshan Alam

In this tutorial, we will learn about the lowest common ancestor in a binary tree in C++. We will also see the pseudocode to how to find LCA in a binary tree.

We will also see examples to understand the concept in a better way.

Find the Lowest common ancestor in a binary tree in C++

The lowest common ancestor(LCA) of two nodes N1 and N2 in a binary tree is the lowest node in a tree that has both node N1 and N2 as a descendant.

Note: A node in a binary tree is also a descendant of itself.

Let’s see the example,

                        1
                      /   \
                     2      6
                     \    /   \
                      3   7     9  Lowest common ancestor of 8 and 9 is 6.
                     /  \  \ 
                   4     5   8

So, in the above example we can understand the lowest common ancestor.

Let’s see the pseudocode

lca(root,n1,n2)
     if root==NULL then return
     if root->data==n1||rott->data==n2 then return root
     recursive call lca(root->left,n1,n2)
     recursive call lca(root->right,n1,n2)
     if left&&right then return root //found lca
     if left&&!right then return left
     if !left&&right then return right
     if !left&&!right then return NULL // yet not found

Now, let’s see the code in C++

Code implementation in C++: LCA in Binary Tree

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct Node{
  int data;
  Node* left;
  Node* right;
};
Node* create(int x){
  Node* temp=new Node;
  temp->data=x;
  temp->left=NULL;
  temp->right=NULL;
  return temp;
}
//function to find lowest common ancestor
Node *lca(Node* root ,int n1 ,int n2 )
{
   if(root==NULL)return NULL;
   if(root->data==n1||root->data==n2)return root;
   Node* left=lca(root->left,n1,n2);
   Node* right=lca(root->right,n1,n2);
   if(!left&&!right)return NULL;
   if(left&&right)return root;//lca found
   if(!left&&right)return right;
   if(!right&&left)return left;
}
//main fuction
int main(){
  Node* root=create(1);
  root->left=create(2);
  root->left->right=create(3);
  root->left->right->left=create(4);
  root->left->right->right=create(5);
  root->right=create(6);
  root->right->left=create(7);
  root->right->left->right=create(8);
  root->right->right=create(9);
  Node* temp=lca(root,8,9);
  if(temp)
  cout<<"LCA of node 8 and 9 is: "<<temp->data<<endl;
  else cout<<" Not found "<<endl;
}

Output

LCA of node 8 and 9 is: 6

You may also learn,

Find out the Diameter of the Binary Tree in C++