#include<iostream>
using namespace std;

template<typename T>
struct Node{
    int key;
    T data;
    Node * left;
    Node * right;
};

template<typename T>
class Tree{
    private:
        Node<T> * root;
        void addNodeRec(int key, int data, Node<T> *(&temp) ){
            if( temp == NULL ){
                temp = new Node<T>;
                temp->key = key;
                temp->data = data;
                temp->left = NULL;
                temp->right = NULL;

                //cout<<"Node added "<<temp->key<<endl;
                //print();
            }else{
                if(temp->key > key){
                    addNodeRec(key, data, temp->left);
                }else{
                    addNodeRec(key, data, temp->right);
                }
            }
        }

        void printNode(Node<T> * root){
            if(root==NULL)return;
            //cout<<"printNode"<<root->key<<endl;
            printNode(root->left);
            cout<<root->key<<" ";
            printNode(root->right);
        }
    public:
        Tree(){root=NULL;}
        void addNode(int key, int data){
            addNodeRec(key, data, this->root);
            ///cout<<root->key<<endl;
        }
        void print(){
            //cout<<"main print"<<endl;
            printNode(this->root);
        }

};

int main(){

    Tree<int> T;
    T.addNode(5,1);
    T.addNode(3,1);
    T.addNode(4,1);
    T.addNode(2,1);
    T.addNode(1,1);
    T.addNode(8,1);
    T.addNode(9,1);
    T.addNode(7,1);
    T.addNode(6,1);

    T.print();
    return 0;
}