#include <iostream>
using namespace std;


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


    Node(int val) {
        data = val;
        left = right = nullptr;
    }
};


// Fungsi untuk menambahkan node
Node* insertBST(Node* root, int data) {
    if (root == nullptr) {
        return new Node(data);
    }


    if (data < root->data) {
        root->left = insertBST(root->left, data);
    } else if (data > root->data) {
        root->right = insertBST(root->right, data);
    }


    return root;
}


// Fungsi untuk mencari node terkecil (untuk penghapusan node)
Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != nullptr) {
        current = current->left;
    }
    return current;
}


// Fungsi untuk menghapus node dari BST
Node* deleteNode(Node* root, int key) {
    if (root == nullptr) return root;


    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        }


        Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }


    return root;
}


// Fungsi inorder traversal
void inorderTraversal(Node* root) {
    if (root == nullptr) return;


    inorderTraversal(root->left);
    cout << root->data << " ";
    inorderTraversal(root->right);
}


int main() {
    Node* root = nullptr;
    root = insertBST(root, 50);
    root = insertBST(root, 30);
    root = insertBST(root, 20);
    root = insertBST(root, 40);
    root = insertBST(root, 70);
    root = insertBST(root, 60);
    root = insertBST(root, 80);


    cout << "Inorder traversal sebelum penghapusan: ";
    inorderTraversal(root);
    cout << endl;


    root = deleteNode(root, 20);


    cout << "Inorder traversal setelah penghapusan: ";
    inorderTraversal(root);


    return 0;
}