i did the same code but for inputs 6 and 7 my output is 1 but it should be 2
code:
#include
#include
using namespace std;
class node{
public:
int data;
nodeleft;
noderight;
node(int d){
data=d;
left=NULL;
right=NULL;
}
};
void bfs2(node* root){
queue<node*> q;
q.push(root);
//null
q.push(NULL);
while(!q.empty()){
node* f=q.front();
if(f==NULL){
cout<<endl;
q.pop();
if(!q.empty()){
q.push(NULL);
}
}
else{
cout<data<<",";
q.pop();
if(f->left){
q.push(f->left);
}
if(f->right){
q.push(f->right);
}
}
}
return;
}
void levelorderbuild(node*&root){
int d;
cin>>d;
root=new node(d);
queue<node*> q;
q.push(root);
while(!q.empty()){
node*f=q.front();
q.pop();
int c1,c2;
//enter the children
cin>>c1>>c2;
if(c1!= -1){
f->left=new node(c1);
q.push(f->left);
}
if(c2!= -1){
f->right=new node(c2);
q.push(f->right);
}
}
}
istream& operator>>(istream& is,node*&root){
//level order print
levelorderbuild(root);
return is;
}
ostream& operator<<(ostream& os,noderoot){
//level order print
bfs2(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;
}
//in left or ryt subtree
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;
cin>>root;
//fxn
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;
}