#include<iostream>
#include<cstdlib>
using namespace std;
typedef struct node
{
struct node* left;
long value;
struct node* right;
}tnode;
tnode* insertnode(long,tnode*);
tnode* createnode(long);
int height(tnode*);
void preorder(tnode*);
int main()
{
int n,i;
cin>>n;
long input[n];
for(i=0;i<n;i++)
{
cin>>input[i];
}
tnode *root=(tnode*)malloc(sizeof(tnode));
root=NULL;
//cout<<"HI"<<endl;
root=insertnode(input[0],root);
for(i=1;i<n;i++)
{
insertnode(input[i],root);
}
preorder(root);
cout<<endl;
cout<<height(root)<<endl;
return 0;
}
tnode* insertnode(long value,tnode* node)
{
if(node==NULL)
{
return createnode(value);
}
else if(value<node->value)
{
node->left=insertnode(value,node->left);
}
else if(value>node->value)
{
node->right=insertnode(value,node->right);
}
}
tnode* createnode(long value)
{
tnode* temp=(tnode*)malloc(sizeof(tnode));
temp->value=value;
temp->left=temp->right=NULL;
return temp;
}
int height(tnode* node)
{
cout<<"Height called for node "<<node->value<<endl;
int lht,rht;
if(node==NULL)
{
return 0;
}
else
{
lht=height(node->left);
rht=height(node->right);
if(lht>=rht)
{
return lht+1;
}
else
{
return rht+1;
}
}
}
void preorder(tnode* temp)
{
if(temp!=NULL)
{
cout<<temp->value<<" ";
preorder(temp->left);
preorder(temp->right);
}
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdGRsaWI+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgc3RydWN0IG5vZGUKewogICAgc3RydWN0IG5vZGUqIGxlZnQ7CiAgICBsb25nIHZhbHVlOwogICAgc3RydWN0IG5vZGUqIHJpZ2h0Owp9dG5vZGU7CnRub2RlKiBpbnNlcnRub2RlKGxvbmcsdG5vZGUqKTsKdG5vZGUqIGNyZWF0ZW5vZGUobG9uZyk7CmludCBoZWlnaHQodG5vZGUqKTsKdm9pZCBwcmVvcmRlcih0bm9kZSopOwppbnQgbWFpbigpCnsKICAgIGludCBuLGk7CiAgICBjaW4+Pm47CiAgICBsb25nIGlucHV0W25dOwogICAgZm9yKGk9MDtpPG47aSsrKQogICAgewogICAgICAgIGNpbj4+aW5wdXRbaV07CiAgICB9CiAgICB0bm9kZSAqcm9vdD0odG5vZGUqKW1hbGxvYyhzaXplb2YodG5vZGUpKTsKICAgIHJvb3Q9TlVMTDsKICAgIC8vY291dDw8IkhJIjw8ZW5kbDsKICAgIHJvb3Q9aW5zZXJ0bm9kZShpbnB1dFswXSxyb290KTsKICAgIGZvcihpPTE7aTxuO2krKykKICAgIHsKICAgICAgICBpbnNlcnRub2RlKGlucHV0W2ldLHJvb3QpOwogICAgfQogICAgcHJlb3JkZXIocm9vdCk7CiAgICBjb3V0PDxlbmRsOwogICAgY291dDw8aGVpZ2h0KHJvb3QpPDxlbmRsOwogICAgcmV0dXJuIDA7Cn0KdG5vZGUqIGluc2VydG5vZGUobG9uZyB2YWx1ZSx0bm9kZSogbm9kZSkKewogICAgaWYobm9kZT09TlVMTCkKICAgIHsKICAgICAgICByZXR1cm4gY3JlYXRlbm9kZSh2YWx1ZSk7CiAgICB9CiAgICBlbHNlIGlmKHZhbHVlPG5vZGUtPnZhbHVlKQogICAgewogICAgICAgIG5vZGUtPmxlZnQ9aW5zZXJ0bm9kZSh2YWx1ZSxub2RlLT5sZWZ0KTsKICAgIH0KICAgIGVsc2UgaWYodmFsdWU+bm9kZS0+dmFsdWUpCiAgICB7CiAgICAgICAgbm9kZS0+cmlnaHQ9aW5zZXJ0bm9kZSh2YWx1ZSxub2RlLT5yaWdodCk7CiAgICB9Cn0KdG5vZGUqIGNyZWF0ZW5vZGUobG9uZyB2YWx1ZSkKewogICAgdG5vZGUqIHRlbXA9KHRub2RlKiltYWxsb2Moc2l6ZW9mKHRub2RlKSk7CiAgICB0ZW1wLT52YWx1ZT12YWx1ZTsKICAgIHRlbXAtPmxlZnQ9dGVtcC0+cmlnaHQ9TlVMTDsKICAgIHJldHVybiB0ZW1wOwp9CmludCBoZWlnaHQodG5vZGUqIG5vZGUpCnsKCWNvdXQ8PCJIZWlnaHQgY2FsbGVkIGZvciBub2RlICI8PG5vZGUtPnZhbHVlPDxlbmRsOwogICAgaW50IGxodCxyaHQ7CiAgICBpZihub2RlPT1OVUxMKQogICAgewogICAgICAgIHJldHVybiAwOwogICAgfQogICAgZWxzZQogICAgewogICAgICAgIGxodD1oZWlnaHQobm9kZS0+bGVmdCk7CiAgICAgICAgcmh0PWhlaWdodChub2RlLT5yaWdodCk7CiAgICAgICAgaWYobGh0Pj1yaHQpCiAgICAgICAgewogICAgICAgICAgICByZXR1cm4gbGh0KzE7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIHJldHVybiByaHQrMTsKICAgICAgICB9CiAgICB9Cn0Kdm9pZCBwcmVvcmRlcih0bm9kZSogdGVtcCkKewogICAgaWYodGVtcCE9TlVMTCkKICAgIHsKICAgICAgICAgICAgY291dDw8dGVtcC0+dmFsdWU8PCIgIjsKICAgICAgICAgICAgcHJlb3JkZXIodGVtcC0+bGVmdCk7CiAgICAgICAgICAgIHByZW9yZGVyKHRlbXAtPnJpZ2h0KTsKICAgIH0KfQ==