C Binary Search Tree 🎯

Welcome to our comprehensive guide on C Binary Search Trees! In this lesson, we'll dive into the world of data structures, focusing on Binary Search Trees (BST) and their practical applications in C programming. By the end of this tutorial, you'll have a solid understanding of this essential data structure.

What is a Binary Search Tree? 📝

A Binary Search Tree (BST) is a type of binary tree data structure where each node has at most two children: the left child and the right child. In a BST, the left subtree contains only nodes with keys less than the parent node, and the right subtree contains nodes with keys greater than the parent node. This property ensures that searching, insertion, and deletion operations are efficient.

Creating a Binary Search Tree Node 💡

Before we can create a BST, we need to define a Node structure. In C, a Node structure could look like this:

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

Here, we've defined a Node structure with three components: key (the value stored in the node), left (the left child), and right (the right child).

Inserting a Node in a BST 💡

Now that we have our Node structure, let's learn how to insert a new node into a BST. The insertion algorithm follows these steps:

Start at the root node.
If the tree is empty, create a new Node and set it as the root.
Otherwise, compare the key of the new node with the root's key.
If the new key is less than the root's key, move to the left subtree and repeat the process.
If the new key is greater than the root's key, move to the right subtree and repeat the process.
When you reach an empty subtree, insert the new node there.

Here's an example of inserting a node with the value 10 into a BST:

struct Node* root = NULL; // Initialize an empty BST

// Inserting 10 into the BST
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->key = 10;
newNode->left = NULL;
newNode->right = NULL;

// Inserting 10 into the empty BST
if (root == NULL) {
    root = newNode;
} else {
    struct Node* current = root;
    while (1) {
        if (newNode->key < current->key) {
            if (current->left == NULL) {
                current->left = newNode;
                break;
            }
            current = current->left;
        } else {
            if (current->right == NULL) {
                current->right = newNode;
                break;
            }
            current = current->right;
        }
    }
}

Searching a Node in a BST 💡

Searching for a node in a BST follows a similar approach as insertion. We start at the root and compare the key of the node we're searching for with the root's key. Depending on the comparison, we move to the left or right subtree and repeat the process until we find the node or reach an empty subtree.

Here's an example of searching for the node with the value 10 in our BST:

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);

    return search(root->left, key);
}

Deleting a Node in a BST 💡

Deleting a node in a BST can be a bit more complex than inserting or searching, especially when dealing with nodes with children or nodes with no children. However, we'll cover the essential cases and provide a complete example.

If the node to be deleted is a leaf node (i.e., it has no children), simply remove it and return.
If the node to be deleted has one child, make the child the new child of the parent node and return.
If the node to be deleted has two children, find the inorder successor (the smallest node in the right subtree) and replace the node to be deleted with the inorder successor.

Here's an example of deleting a node with the value 10 from our BST:

struct Node* delete(struct Node* root, int key) {
    if (root == NULL)
        return root;

    if (key < root->key)
        root->left = delete(root->left, key);
    else if (key > root->key)
        root->right = delete(root->right, key);
    else {
        if (root->left == NULL)
            return root->right;
        else if (root->right == NULL)
            return root->left;

        // Find the inorder successor
        struct Node* successor = findMin(root->right);

        // Copy the inorder successor's data to the node to be deleted
        root->key = successor->key;

        // Delete the inorder successor
        root->right = delete(root->right, successor->key);
    }
    return root;
}

// Helper function to find the minimum node in the BST
struct Node* findMin(struct Node* node) {
    if (node->left == NULL)
        return node;
    return findMin(node->left);
}

Quiz 🎯

Now that you've learned the basics of C Binary Search Trees, you're well-equipped to implement them in your own projects. Practice these concepts and keep exploring to master this essential data structure!

Happy coding! 🚀💻💻