#include
#include
using namespace std;
class node{
public:
int data;
nodeleft;
noderight;
node(int d){
data = d;
left = NULL;
right = NULL;
}
};
void levelOrderBuild(node*&root){
int d;
cin>>d;
root=new node(d);
queue<node*> q;
q.push(root);
while(!q.empty()){
node*n=q.front();
q.pop();
int c1,c2;
cin>>c1>>c2;
if(c1!=-1){
n->left=new node(c1);
q.push(n->left);
}
if(c2!=-1){
n->right=new node(c2);
q.push(n->right);
}
}
}
void levelOrderPrint(node*root){
queue<node*> q;
q.push(root);
q.push(NULL);
while(!q.empty()){
node*n = q.front();
if(n==NULL){
cout<<endl;
q.pop();
if(!q.empty()){
q.push(NULL);
}
}
else{
q.pop();
cout<data<<" ";
if(n->left){
q.push(n->left);
}
if(n->right){
q.push(n->right);
}
}
}
}
istream& operator>>(istream&is,node*root){
levelOrderBuild(root);
return is;
}
ostream& operator<<(ostream&os,node*root){
levelOrderPrint(root);
return os;
}
node* lca(node*root,int a,int b){
if(root==NULL){
return NULL;
}
if(root->data==a or root->data==b){
return root;
}
//search in left and right subtrees
node* leftans=lca(root->left,a,b);
node* rightans=lca(root->right,a,b);
if(leftans!=NULL and rightans!=NULL){
return root;
}
if(leftans!=NULL){
return leftans;
}
return rightans;
}
int main(){
node* root= NULL;
//take input the tree
cin>>root;
int a=7,b=9;
cout<<“LCA of 4 and 7 is”<<lca(root,4,7)->data<<endl;
cout<<“LCA of 6 and 9 is”<<lca(root,6,9)->data<<endl;
return 0;
}