#Algorithm Sort

treeDelete

#include <iostream>

using namespace std;

class Node{
public:
    int value;
    Node* left;
    Node* right;

    Node() : value(0), left(NULL), right(NULL) {}
    Node(int x) : value(x), left(NULL), right(NULL) {}
    Node(int x, Node* left, Node* right) : value(x), left(left), right(right) {}
};


Node* deleteNode(Node* r, int x){

    if(r==NULL)return NULL;
    else if(r->value<x)
    {
        r->right = deleteNode(r->right,x);
        return r;
    }
    else if(r->value>x){
        r->left = deleteNode(r->left,x);
        return r;
    }
    else{
        if (r->left == NULL && r->right == NULL)
            return NULL;

        else if (r->left == NULL && r->right != NULL)
            return r->right;

        else if (r->left != NULL && r->right == NULL)
            return r->left;

        else {
            Node *s = r->right;
            Node *parent;

            while (s->left != NULL) {
                parent = s;
                s = s->left;
            }
            r->value = s->value;

            if (s == r->right) {
                r->right = s->right;
            }
            else {
                parent->left = s->right;
            }
            return r;
        }
    }
}

Node* treeInsert(Node * t, int value){
    if(t == NULL){
        Node* newNode = new Node(value);
        return newNode;
    }
    if(value < t->value){
        t->left = treeInsert(t->left, value);
        return t;
    }
    else{
        t->right = treeInsert(t->right, value);
        return t;
    }
}

void ZeroNodeValue(Node *r){
    if(r != NULL){
        cout << r->value << ' ';
        ZeroNodeValue(r->left);
        ZeroNodeValue(r->right);
    }
}

void oneNodeValue(Node *r){
    if(r != NULL){
        oneNodeValue(r->left);
        cout << r->value << ' ';
        oneNodeValue(r->right);
    }

}

void twoNodeValue(Node *r){
    if(r != NULL){
        twoNodeValue(r->left);
        twoNodeValue(r->right);
        cout << r->value << ' ';
    }
}


int main() {
    int n;
    int x;
    int Cremove;
    int remove;
    int p;


    Node* root = NULL;


    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> x;
        root = treeInsert(root, x);
    }

    cin >> Cremove;

    for(int i = 0; i < Cremove; i++){
        cin >> p >> remove;

        root = deleteNode(root, remove);

        if(p == 0){
            ZeroNodeValue(root);
        }
        else if(p == 1){
            oneNodeValue(root);
        }

        else if(p == 2){
            twoNodeValue(root);
        }
        cout << '\n';
    }

    return 0;
}