#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);
    inorder(root->rightChild);
}
void insertNode(int value)
{
    node *tempNode;
    node *currentNode=NULL;
    node *parentNode=NULL;

    tempNode = (node *) malloc(sizeof(node));
    tempNode->number = value;

    //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);
}