Is_Balanced ( Binary Tree )

#1

can you tell me the second test case

#2

Hi @sanyamsri2001
Please provide your code so that i can have a look and come up with the reason why your code failed the test case.

#3

https://codeshare.io/G7jBob

#4

Hi @sanyamsri2001
you have to make 2 changes :

  1. In the build tree function you are taking input which is a string value and you are passing it to function call which is a bool variable which is wrong. instead you have to take string as input and then if it is true then pass 1 as argument else pass 0.
  2. In bbt function when root is NULL its height is 0 not -1.

Corrected Code :
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node *left;
node *right;
node(int d){
data=d;
left=NULL;
right=NULL;
}
};
node *buildtree(bool ans){
if(ans){
string s;
int data;
cin>>data;
node *root=new node(data);
cin>>s;
if(s==“true”)
root->left=buildtree(1);
if(s==“false”)
root->left=buildtree(0);
cin>>s;
if(s==“true”)
root->right=buildtree(1);
if(s==“false”)
root->right=buildtree(0);
return root;
}
else{
return NULL;
}
}
struct pai{
int height;
bool ch;
};

pai bbt(node *n){
pai p;
if(n==NULL){
p.ch=1;
p.height=0;
return p;
}
pai left=bbt(n->left);
pai right=bbt(n->right);
int d=abs(left.height-right.height);
if(left.ch && right.ch && d<=1){
p.ch=1;
}
else{
p.ch=0;
}
p.height=max(left.height,right.height)+1;//important to add 1
return p;
}

int main(){
node *root=buildtree(1);
pai p;
p=bbt(root);
if(p.ch)
cout<<“true”;
else{
cout<<“false”;
}
return 0;
}