BST

#include<iostream>
using namespace std;
struct node{
int val;
node *left;
node *right;
node(){
val=0;
left=right=NULL;
}
};
class BST{
private: node *ROOT;
public:
    BST();
    void insert1(int x);
    void insert2(node *r,int x);
    void print();
};

BST::BST(){
ROOT=NULL;
}
void BST::insert1(int x)
{
insert2(ROOT,x);
}
void BST::insert2(node *r,int x)
{
    if(r==NULL){
        node *n=new node();
        n->val=x;
        ROOT=n;
        return;
    }
    if(x<=r->val){
        if(r->left==NULL){
            node *n=new node();
            n->val=x;
            r->left=n;
            return;

        }
        else {
            insert2(r->left,x);
            return;
        }
    }
    else{
        if(r->right==NULL){
            node *n=new node();
            n->val=x;
            r->right=n;
            return;
        }
        else{
            insert2(r->right,x);
            return;
        }
    }
}
void BST::print(){
node *cur=ROOT;
while(cur!=NULL){
    cout<<cur->val<<" ";
    cur=cur->left;
}
}
int main()
{
    BST *m=new BST();
    m->insert1(4);
    m->insert1(2);
    m->insert1(1);
    m->insert1(5);
    m->insert1(6);
    m->insert1(9);
    m->insert1(0);
    m->print();
}