Untitled

#include <iostream>
//#include <string>

using namespace std;
int sum_tree;
// Cấu trúc của một node trong BST
struct Node {
	int data;
	Node* left;
	Node* right;

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

// Hàm chèn một phần tử vào BST
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;
}

// Hàm findNode để duyệt cây
int findNode(Node* root, int x) {
	if(root == NULL)
	{
		return 0;
	}
	else
	{
		if(root->data == x)
			return 1;
		else if(root->data > x)
		{
			return findNode(root->left, x);
		}
		else
		{
			return findNode(root->right, x);
		}
	}
}

// Hàm tìm lower_bound (giá trị lớn hơn hoặc bằng value)
Node* lower_bound(Node* root, int value) {
	Node* result = nullptr;
	Node* tmp = root;
	while (tmp != nullptr) {
		if (tmp->data >= value) {
			result = tmp;  // Cập nhật node hiện tại
			tmp = tmp->left;  // Tìm tiếp trong cây con trái
		} else {
			tmp = tmp->right;  // Tìm tiếp trong cây con phải
		}
	}
	return result;
}

// Hàm tìm upper_bound (giá trị nhor hơn value)
Node* upper_bound(Node* root, int value) {
	Node* result = nullptr;
	Node* tmp = root;
	while (tmp != nullptr) {
		if (tmp->data < value) {
			result = tmp;  // Cập nhật node hiện tại
			tmp = tmp->right;  // Tìm tiếp trong cây con trái
		} else {
			tmp = tmp->left;  // Tìm tiếp trong cây con phải
		}
	}
	return result;
}
// Hàm tìm giá trị nhỏ nhất trong cây con phải (successor)
Node* findMin(Node* root) {
    while (root->left != nullptr) {
        root = root->left;
    }
    return root;
}
// Hàm xóa một phần tử trong BST
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 {
		// Trường hợp tìm thấy nút cần xóa
		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;
		}

		// Trường hợp có hai con: tìm successor (nút nhỏ nhất của cây con phải)
		Node* temp = findMin(root->right);
		root->data = temp->data;  // Thay thế bằng successor
		root->right = deleteNode(root->right, temp->data);  // Xóa successor
	}

	return root;
}
int main(int argc, char** argv)
{
	int test_case;
	int T;
	/* 
	The freopen function below opens input.txt in read only mode and 
	sets your standard input to work with the opened file. 
	When you test your code with the sample data, you can use the function
	below to read in from the sample data file instead of the standard input.
	So. you can uncomment the following line for your local test. But you
	have to comment the following line when you submit for your scores.
	*/

	//freopen("Text.txt", "r", stdin);
	cin>>T;

	/*
	Read each test case from standard input.
	*/
	for(test_case = 1; test_case <= T; ++test_case)
	{

		int n;
		cin >> n;
		Node* root = nullptr;
		sum_tree = 0;
		cout << "#" << test_case << " ";
		for(int i = 0; i < n; i++)
		{
			string lenh;
			cin >> lenh;
			if(lenh != "size")
			{
				int x;
				cin >> x;
				if(lenh == "add")
				{
					root = insert(root,x);
				}
				else if(lenh == "remove")
				{
					deleteNode(root,x);
				}
				else if(lenh == "contains")
				{
					bool found = findNode(root,x);
					cout << (found == 1 ? "true" : "false" ) << " ";
				}
				else if(lenh == "lower")
				{
					Node* tmp = upper_bound(root,x);
					tmp == NULL ? cout << "null " : cout << tmp->data << " ";
				}
				else
				{
					Node* tmp = lower_bound(root,x);
					tmp == NULL ? cout << "null " : cout << tmp->data << " ";
				}
			}
			else
			{
				cout << sum_tree << " ";
			}
		}
		cout << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}