#include <iostream>





template<typename T>
class BST {
    struct Node {
        int key; //키
        T value; //값
        Node* left; //자식 노드 -> 왼쪽
        Node* right; // 자식 노드 -> 오른쪽
        int leftSize; // 왼쪽 서브트리의 크기

        Node(int k, T val) : key(k), value(val), left(nullptr), right(nullptr), leftSize(0) {}
    };
    Node* root; // 루트 노드(트리)


    //1번 조건
    Node* insert(Node* node, int key, T val) {
        if (!node) return new Node(key, val);
        if (key < node->key) {
            node->left = insert(node->left, key, val);
            node->leftSize++;
        } else {
            node->right = insert(node->right, key, val);
        }
        return node;
    }


    void inorder(Node* node) {
        if (!node) return;
        inorder(node->left);
        std::cout << "(" << node->key << ", " << node->value << ") "; //현재 노드 출력
        inorder(node->right);
    }

    Node* get(Node* node, int key) {
        if (!node || node->key == key) return node;
        //양쪽 서브트리 탐색ㅎ기ㅡ
        if (key < node->key) return get(node->left, key); 
        return get(node->right, key);
    }


//노드 삭제하는 부분만들
    Node* removeNode(Node* node, int key) {
        if (!node) return node;

        if (key < node->key) {
            node->left = removeNode(node->left, key);
        } else if (key > node->key) {
            node->right = removeNode(node->right, key);
        } else {

            //3번 & 6번 & 8 조건
            
            if (!node->left) {
                Node* temp = node->right;
                
                delete node; //노드 삭제
                
                return temp;
            } else if (!node->right) {
                Node* temp = node->left;
                
                delete node; //노드 삭제
                
                return temp;
            }

            //4번 & 5번 & 7번 조건 
            Node* temp = minValueNode(node->right);
            node->key = temp->key;
            node->right = removeNode(node->right, temp->key);
        }
        return node;
    }


    Node* minValueNode(Node* node) {
        Node* current = node;
        while (current && current->left != nullptr)
            current = current->left;
        return current;
    }





public:
    BST() : root(nullptr) {}

    void insert(int key, T val) {
        root = insert(root, key, val);
    }

    void inorder() {
        inorder(root);
        std::cout << std::endl;
    }

    Node* get(int key) {
        return get(root, key);
    }

    void remove(int key) {
        root = removeNode(root, key);
    }

    ~BST() {
        deleteNode(root);
    }

    void deleteNode(Node* node) {
        if (!node) return;
        //9번 조건 
        deleteNode(node->left);
        deleteNode(node->right);
        delete node;
    }
};

int main() {
    BST<int> bst;

    //순서대로 노드 삽입
    bst.insert(33, 90);
    bst.insert(50, 73);
    bst.insert(43, 99);
    bst.insert(11, 82);
    bst.insert(24, 78);
    bst.insert(46, 96);
    bst.insert(1, 72);
    bst.insert(8, 88);
    bst.insert(36, 77);
    bst.insert(56, 93);
    bst.insert(53, 82);
    bst.insert(59, 100);

    // 중위 순회 출력
    std::cout << "Inorder traversal: ";
    bst.inorder();

    //노드 삭제(remove로) + 중위 순회 출력
    bst.remove(50);
    std::cout << "After removing 50: ";
    bst.inorder();

    bst.remove(8);
    std::cout << "After removing 8: ";
    bst.inorder();

    bst.remove(56);
    std::cout << "After removing 56: ";
    bst.inorder();

    //특정 노드 검색
    auto node = bst.get(43);
    if (node) {
        std::cout << "Node with key 43 found: (" << node->key << ", " << node->value << ")\n";
    } else {
        std::cout << "Node with key 43 not found.\n";
    }

    return 0;
}