Untitled

#include <iostream>
using namespace std;

struct node {
    int data;
    struct node *pLeft;
    struct node *pRight;
};

typedef struct node NODE;
typedef NODE *TREE;

int sum_tree; // Track the number of nodes

// Initialize the tree
void init(TREE &t) {
    t = NULL;
}

// Function to add an element to the binary search tree (BST)
void add_tree(TREE &t, int x) {
    if (t == NULL) {
        NODE *p = new NODE;
        p->data = x;
        p->pLeft = p->pRight = NULL;
        t = p;
        sum_tree++; // Increase the count of nodes
    } else {
        if (t->data > x) {
            add_tree(t->pLeft, x);
        } else if (t->data < x) {
            add_tree(t->pRight, x);
        }
        // If x already exists, do nothing
    }
}

// Function to find a node with value x in the tree
bool find_node(TREE &t, int x) {
    if (t == NULL) {
        return false;
    }
    if (t->data == x) {
        return true;
    } else if (t->data < x) {
        return find_node(t->pRight, x);
    } else {
        return find_node(t->pLeft, x);
    }
}

// Function to remove a node with value x
int remove_node(TREE &t, int x) {
    if (t == NULL) {
        return 0;
    }
    if (t->data > x) {
        return remove_node(t->pLeft, x);
    } else if (t->data < x) {
        return remove_node(t->pRight, x);
    } else { // Node found
        if (t->pLeft == NULL && t->pRight == NULL) { // Leaf node
            delete t;
            t = NULL;
        } else if (t->pLeft == NULL) { // Node with one right child
            NODE *tmp = t;
            t = t->pRight;
            delete tmp;
        } else if (t->pRight == NULL) { // Node with one left child
            NODE *tmp = t;
            t = t->pLeft;
            delete tmp;
        } else { // Node with two children
            NODE *tmp = t->pRight;
            while (tmp->pLeft != NULL)
                tmp = tmp->pLeft;
            t->data = tmp->data;
            return remove_node(t->pRight, tmp->data);
        }
        sum_tree--; // Decrease the count of nodes
        return 1;
    }
}

// Optimized upper_bound function
int upper_bound(TREE &t, int x) {
    NODE *result = NULL;
    NODE *tmp = t;
    while (tmp != NULL) {
        if (tmp->data < x) {
            result = tmp;
            tmp = tmp->pRight;
        } else {
            tmp = tmp->pLeft;
        }
    }
    return result ? result->data : 0;
}

// Optimized lower_bound function
int lower_bound(TREE &t, int x) {
    NODE *result = NULL;
    NODE *tmp = t;
    while (tmp != NULL) {
        if (tmp->data >= x) {
            result = tmp;
            tmp = tmp->pLeft;
        } else {
            tmp = tmp->pRight;
        }
    }
    return result ? result->data : 0;
}

int main(int argc, char** argv) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int test_case;
    int T;
    cin >> T;

    for (test_case = 1; test_case <= T; ++test_case) {
        int n;
        cin >> n;
        TREE t;
        sum_tree = 0;
        init(t);
        cout << "#" << test_case << " ";
        for (int i = 0; i < n; i++) {
            string command;
            cin >> command;
            if (command != "size") {
                int x;
                cin >> x;
                if (command == "add") {
                    add_tree(t, x);
                } else if (command == "remove") {
                    remove_node(t, x);
                } else if (command == "contains") {
                    bool found = find_node(t, x);
                    cout << (found ? "true" : "false") << " ";
                } else if (command == "lower") {
                    int tmp = upper_bound(t, x);
                    cout << (tmp == 0 ? "null " : to_string(tmp) + " ");
                } else {
                    int tmp = lower_bound(t, x);
                    cout << (tmp == 0 ? "null " : to_string(tmp) + " ");
                }
            } else {
                cout << sum_tree << " ";
            }
        }
        cout << endl;
    }
    return 0;
}