nhom2

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node* left;
    Node* right;
};

class BST {
public:
    BST() {
        root = NULL;
    }

    void insert(int value) {
        Node* newNode = new Node;
        newNode->value = value;
        newNode->left = NULL;
        newNode->right = NULL;

        if (root == NULL) {
            root = newNode;
        } else {
            Node* currentNode = root;
            while (true) {
                if (value < currentNode->value) {
                    if (currentNode->left == NULL) {
                        currentNode->left = newNode;
                        break;
                    } else {
                        currentNode = currentNode->left;
                    }
                } else {
                    if (currentNode->right == NULL) {
                        currentNode->right = newNode;
                        break;
                    } else {
                        currentNode = currentNode->right;
                    }
                }
            }
        }
    }

    bool search(int value) {
        Node* currentNode = root;
        while (currentNode != NULL) {
            if (currentNode->value == value) {
                return true;
            } else if (value < currentNode->value) {
                currentNode = currentNode->left;
            } else {
                currentNode = currentNode->right;
            }
        }
        return false;
    }

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

    void print() {
        printHelper(root);
        cout << endl;
    }

private:
    Node* root;

    void printHelper(Node* node) {
        if (node != NULL) {
            printHelper(node->left);
            cout << node->value << " ";
            printHelper(node->right);
        }
    }

    Node* removeHelper(Node* node, int value) {
        if (node == NULL) {
            return NULL;
        } else if (value < node->value) {
            node->left = removeHelper(node->left, value);
        } else if (value > node->value) {
            node->right = removeHelper(node->right, value);
        } else {
            if (node->left == NULL && node->right == NULL) {
                delete node;
                node = NULL;
            } else if (node->left == NULL) {
                Node* temp = node;
                node = node->right;
                delete temp;
            } else if (node->right == NULL) {
                Node* temp = node;
                node = node->left;
                delete temp;
            } else {
                Node* temp = findMin(node->right);
                node->value = temp->value;
                node->right = removeHelper(node->right, temp->value);
            }
        }
        return node;
    }

    Node* findMin(Node* node) {
        while (node->left != NULL) {
            node = node->left;
        }
        return node;
    }
};

int main() {
    BST bst;
    bst.insert(4);
    bst.insert(2);
    bst.insert(6);
    bst.insert(1);
    bst.insert(3);
    bst.insert(5);
    bst.insert(7);

    bst.print(); // Output: 1 2 3 4 5 6 7

    cout << bst.search(6) << endl; // Output: 1 (true)
    cout << bst.search(8) << endl; // Output: 0 (false)

    bst.remove(