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

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;
`LCA of node 8 and 9 is: 6`