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; else cout<<" Not found "<<endl; }
Output
LCA of node 8 and 9 is: 6
You may also learn,
Leave a Reply