my output doesnt match .pls check
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;
}
//search for the level
int search(node*root,int key,int level){
if(root==NULL){
return -1;
}
if(root->data==key){
return level;
}
int left=search(root->left,key,level+1);
if(left!= -1){
return left;
}
return search(root->right,key,level+1);
}
//find distance
int findDist(noderoot,int a,int b){
node lca_node=lca(root,a,b);
int l1=search(lca_node,a,0);
int l2=search(lca_node,b,0);
return l1+l2;
}
int main(){
node*root=NULL;
cin>>root;
//fxn
cout<<"dist btw 4 and 7 is "<<findDist(root,4,7)<<endl;
cout<<"dist btw 6 and 9 is "<<findDist(root,6,9)<<endl;
return 0;
//input-1 2 4 6 -1 -1 7 10 -1 -1 11 -1 -1 5 8 -1 -1 9 -1 -1 3 -1 -1
}