#include<iostream>
#include<malloc.h>
using namespace std;
typedef struct tree
{
int number;
struct tree *leftChild;
struct tree *rightChild;
} node;
node *root=NULL;
void inorder(node *root){
if(root==NULL)
return;
inorder(root->leftChild);
printf("%d ", root->number);
inorder(root->rightChild);
}
void insertNode(int value)
{
node *tempNode;
node *currentNode=NULL;
node *parentNode=NULL;
tempNode = (node *) malloc(sizeof(node));
tempNode->number = value;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//For the very first call
if(root==NULL)
{
root = tempNode;
}
else
{
currentNode = root;
parentNode = NULL;
while(1)
{
parentNode = currentNode;
if(value <= parentNode->number)
{
currentNode = currentNode->leftChild;
if(currentNode==NULL)
{
parentNode->leftChild = tempNode;
return;
}
}
else
{
currentNode = currentNode->rightChild;
if(currentNode==NULL)
{
parentNode->rightChild = tempNode;
return;
}
}
}
}
}
int main()
{
int total_node;
cout<<"Enter total node amount:\n";
cin>>total_node;
for(int i=1; i<=total_node; i++) insertNode(i);
cout<<endl;
inorder(root);
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPG1hbGxvYy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0eXBlZGVmIHN0cnVjdCB0cmVlCnsKICAgIGludCBudW1iZXI7CiAgICBzdHJ1Y3QgdHJlZSAqbGVmdENoaWxkOwogICAgc3RydWN0IHRyZWUgKnJpZ2h0Q2hpbGQ7Cgp9IG5vZGU7Cm5vZGUgKnJvb3Q9TlVMTDsKCnZvaWQgaW5vcmRlcihub2RlICpyb290KXsKICAgIGlmKHJvb3Q9PU5VTEwpCiAgICAgICAgcmV0dXJuOwoKICAgIGlub3JkZXIocm9vdC0+bGVmdENoaWxkKTsKCiAgICBwcmludGYoIiVkICIsIHJvb3QtPm51bWJlcik7CgogICAgaW5vcmRlcihyb290LT5yaWdodENoaWxkKTsKfQoKdm9pZCBpbnNlcnROb2RlKGludCB2YWx1ZSkKewogICAgbm9kZSAqdGVtcE5vZGU7CiAgICBub2RlICpjdXJyZW50Tm9kZT1OVUxMOwogICAgbm9kZSAqcGFyZW50Tm9kZT1OVUxMOwoKICAgIHRlbXBOb2RlID0gKG5vZGUgKikgbWFsbG9jKHNpemVvZihub2RlKSk7CiAgICB0ZW1wTm9kZS0+bnVtYmVyID0gdmFsdWU7CiAgICB0ZW1wTm9kZS0+bGVmdENoaWxkID0gTlVMTDsKICAgIHRlbXBOb2RlLT5yaWdodENoaWxkID0gTlVMTDsKCiAgICAvL0ZvciB0aGUgdmVyeSBmaXJzdCBjYWxsCiAgICBpZihyb290PT1OVUxMKQogICAgewogICAgICAgIHJvb3QgPSB0ZW1wTm9kZTsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBjdXJyZW50Tm9kZSA9IHJvb3Q7CiAgICAgICAgcGFyZW50Tm9kZSA9IE5VTEw7CgogICAgICAgIHdoaWxlKDEpCiAgICAgICAgewogICAgICAgICAgICBwYXJlbnROb2RlID0gY3VycmVudE5vZGU7CgogICAgICAgICAgICBpZih2YWx1ZSA8PSBwYXJlbnROb2RlLT5udW1iZXIpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGN1cnJlbnROb2RlID0gY3VycmVudE5vZGUtPmxlZnRDaGlsZDsKCiAgICAgICAgICAgICAgICBpZihjdXJyZW50Tm9kZT09TlVMTCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBwYXJlbnROb2RlLT5sZWZ0Q2hpbGQgPSB0ZW1wTm9kZTsKICAgICAgICAgICAgICAgICAgICByZXR1cm47CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBjdXJyZW50Tm9kZSA9IGN1cnJlbnROb2RlLT5yaWdodENoaWxkOwoKICAgICAgICAgICAgICAgIGlmKGN1cnJlbnROb2RlPT1OVUxMKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHBhcmVudE5vZGUtPnJpZ2h0Q2hpbGQgPSB0ZW1wTm9kZTsKICAgICAgICAgICAgICAgICAgICByZXR1cm47CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KCiAgICAgICAgfQogICAgfQp9CmludCBtYWluKCkKewogICAgaW50IHRvdGFsX25vZGU7CiAgICBjb3V0PDwiRW50ZXIgdG90YWwgbm9kZSBhbW91bnQ6XG4iOwogICAgY2luPj50b3RhbF9ub2RlOwogICAgZm9yKGludCBpPTE7IGk8PXRvdGFsX25vZGU7IGkrKykgaW5zZXJ0Tm9kZShpKTsKICAgIGNvdXQ8PGVuZGw7CiAgICBpbm9yZGVyKHJvb3QpOwp9Cg==