
void insert(int k){
    struct Node *y = NIL;
    struct Node *x = root;
    struct Node *z;

    z = (struct Node *)malloc(sizeof(struct Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;
    

    while(x!= NIL){
        y = x;
        if(z->key < x->key){
            x = x->left;
        } else{
            x = x->right;
        }
    }
    
    z->parent = y;
    if(y == NIL){
        root = z;
    } else{
        if( z->key < y->key){
            y->left = z;
        } else{
            y->right = z;
        }
    }

}
