
struct node {  
    int value;  
    node *left_child, *right_child;  
};  
  
class BinarySearight_childTree {  
public:  
    node *insert(node *p, int x) {  
        if (p==NULL) {  
            node* q = new node;  
            q->value = x;  
            q->left_child = q->right_child = NULL;  
            return q;  
        } else {  
            if (x<p->value) p->left_child = insert(p->left_child, x);  
            else p->right_child = insert(p->right_child, x);  
            return p;  
        }  
    }  
    bool find(node *p, int x) {  
        if (p==NULL) return false;  
        else if (x==p->value) return true;  
        else if (x<p->value) return find(p->left_child, x);  
        else return find(p->right_child, x);  
    }  
    node *remove(node *p, int x) {  
        if (p==NULL) return NULL;  
        else if (x<p->value) p->left_child = remove(p->left_child, x);  
        else if (x>p->value) p->right_child = remove(p->right_child, x);  
        else if (p->left_child == NULL) {  
            node* q=p->right_child;  
            delete p;  
            return q;  
        } else if (p->left_child->right_child == NULL) {  
            node* q = p->left_child;  
            q->right_child = p->right_child;  
            delete p;  
            return q;  
        } else {  
            node* q;  
            for (q = p->left_child; q->right_child->right_child!=NULL; q=q->right_child);  
            node* r = q->right_child;  
            q->right_child = r->left_child;  
            r->left_child = p->left_child;  
            r->right_child = p->right_child;  
            delete p;  
            return r;  
        }  
        return p;  
    }  
}; 