Untitled

#include <iostream> 
#include <string> 
#include <ios>

using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;

    // Constructor
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

// BST class to encapsulate operations and state
class BST {
private:
    Node* root;
    int sum_tree;

    Node* insert(Node* root, int value) {
        if (root == nullptr) {
            sum_tree++;
            return new Node(value);
        }
        if (value < root->data) {
            root->left = insert(root->left, value);
        } else if (value > root->data) {
            root->right = insert(root->right, value);
        }
        return root;
    }

    Node* findMin(Node* root) {
        while (root->left != nullptr) {
            root = root->left;
        }
        return root;
    }

    Node* deleteNode(Node* root, int value) {
        if (root == nullptr) return root;
        if (value < root->data) {
            root->left = deleteNode(root->left, value);
        } else if (value > root->data) {
            root->right = deleteNode(root->right, value);
        } else {
            // Node found
            if (root->left == nullptr) {
                sum_tree--;
                Node* temp = root->right;
                delete root;
                return temp;
            } else if (root->right == nullptr) {
                sum_tree--;
                Node* temp = root->left;
                delete root;
                return temp;
            }
            // Two children
            Node* temp = findMin(root->right);
            root->data = temp->data;
            root->right = deleteNode(root->right, temp->data);
        }
        return root;
    }

    bool findNode(Node* root, int x) {
        if (root == nullptr) {
            return false;
        }
        if (root->data == x) {
            return true;
        } else if (root->data > x) {
            return findNode(root->left, x);
        } else {
            return findNode(root->right, x);
        }
    }

    Node* lower_bound(Node* root, int value) {
        Node* result = nullptr;
        Node* tmp = root;
        while (tmp != nullptr) {
            if (tmp->data >= value) {
                result = tmp;
                tmp = tmp->left;
            } else {
                tmp = tmp->right;
            }
        }
        return result;
    }

    Node* upper_bound(Node* root, int value) {
        Node* result = nullptr;
        Node* tmp = root;
        while (tmp != nullptr) {
            if (tmp->data < value) {
                result = tmp;
                tmp = tmp->right;
            } else {
                tmp = tmp->left;
            }
        }
        return result;
    }

public:
    BST() : root(nullptr), sum_tree(0) {}

    void add(int value) {
        root = insert(root, value);
    }

    void remove(int value) {
        root = deleteNode(root, value);
    }

    bool contains(int value) {
        return findNode(root, value);
    }

    int size() {
        return sum_tree;
    }

    int lower(int value) {
        Node* tmp = upper_bound(root, value);
        return tmp == nullptr ? -1 : tmp->data;
    }

    int upper(int value) {
        Node* tmp = lower_bound(root, value);
        return tmp == nullptr ? -1 : tmp->data;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;

    for (int test_case = 1; test_case <= T; ++test_case) {
        int n;
        cin >> n;
        BST tree;
        cout << "#" << test_case << " ";
        for (int i = 0; i < n; i++) {
            string command;
            cin >> command;
            if (command == "size") {
                cout << tree.size() << " ";
            } else {
                int x;
                cin >> x;
                if (command == "add") {
                    tree.add(x);
                } else if (command == "remove") {
                    tree.remove(x);
                } else if (command == "contains") {
                    cout << (tree.contains(x) ? "true" : "false") << " ";
                } else if (command == "lower") {
                    int res = tree.lower(x);
                    cout << (res == -1 ? "null" : to_string(res)) << " ";
                } else if (command == "upper") {
                    int res = tree.upper(x);
                    cout << (res == -1 ? "null" : to_string(res)) << " ";
                }
            }
        }
        cout << endl;
    }
    return 0;
}