Binary search tree adalah binary tree yang menggunakan node dan memiliki beberapa properti yaitu:

1. Node anak kiri berisikan angka lebih kecil dari node induk
2. Node anak kanan berisikan angka lebih besar dari node induk
3. Node kanan dan kiri juga harus merupakan binary search tree
4. tidak boleh ada node yang duplicate /sama

Operasi pada binary search tree:

1. find(); mencari sebuah angka/data pada binary search tree
2. insert(): memasukkan angka/data baru pada binary search tree
3. remove():menghapus angka/data baru pada binary search tree

Searching: untuk melakukan searching pertama kita mengcompare nodenya , apabila angka/data yang dicari ada pada node maka kita akan return node, apabila angka yang ingin dicari lebih besar makan kita akan mengcompare node anak kanan sedangkan apabila lebih kecil kita akan mengcompare anak node kiri.

struct node* search(struct node* root, int key)
{
    if (root == NULL || root->key == key)
       return root;
    if (root->key < key)
       return search(root->right, key); //kalo lebih besar
    return search(root->left, key); // kalo lebih kecil
}

Insertion: sama seperti searching, insertion melakukan compare root apabila angka yang ingin diinsert lebih besar maka akan pindah ke kanan sedangkan kalo kecil ke kiri, apabila angka yang ingin diinsert ditemukan sama dengan root maka akan return false/true.dilakukan sampai menemukan node kosong untuk x

struct node* insert(struct node* node, int key)
{
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(key);
 
    /* Otherwise, recur down the tree */
    if (key < node->key)
        node->left  = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);   
 
    /* return the (unchanged) node pointer */
    return node;
}

Deletion : apabila yang dihapus merupakan anak node paling bawah maka langsung delete, apabila yang ingin dihapus hanya memiliki 1 anak node maka copy anak node ke node induk kemudian delete node anak,apabila yang ingin dihapus memiliki 2 anak maka akan mencari succesor dari node
kemudian mengcopy anak node ke succesor node, succesor node bisa berupa node paling kiri dari subtree kanan ataupun node paling kanan dari subtree kiri.
struct node* deleteNode(struct node* root, int key)
{

    if (root == NULL) return root;
 
 
    if (key < root->key)
        root->left = deleteNode(root->left, key);
 

    else if (key > root->key)
        root->right = deleteNode(root->right, key);
 

    else
    {
        if (root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }
 
        struct node* temp = minValueNode(root->right);
 

        root->key = temp->key;

        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}