BST Operations: Insert and Search

Welcome to the next lesson in our journey through data structures! In our previous session, we defined the Binary Search Tree (BST) and understood its core properties: for any node, all values in its left subtree are smaller, and all values in its right subtree are larger. We also saw why this structure is so promising for efficient data management.

Today, we'll bring that theory to life. Our goal is to implement the fundamental insert and search operations for a BST in C. You'll write the code that enforces the BST properties and leverages them to find data quickly. This lesson is all about translating a recursive, logical concept into concrete, working functions.

1. The Building Block: A Node struct

Before we can insert or search, we need a way to represent a tree node in C. As you'll recall from Module 5, structs are perfect for grouping related data. For a BST node, we need to store three things:

1. The data itself (we'll use an integer).
2. A pointer to the left child node.
3. A pointer to the right child node.

We will also use dynamic memory allocation (malloc) to create these nodes on the heap as we need them.

The following video provides an excellent review of how to define a node struct for a tree and how to think about the collection of nodes forming a tree, which is managed through a single root pointer.

Based on this, our C struct for a node will look like this:

#include <stdlib.h> // For malloc and free

struct node {
    int data;
    struct node *left;
    struct node *right;
};

And to start, our tree is empty, represented by a null pointer:
struct node *root = NULL;

2. The Insert Operation

The insert operation is where we enforce the BST property. The core idea is to find the correct empty spot (NULL pointer) to attach a new node.

The Algorithm

The process is naturally recursive:

1. Start at the root of the tree (or subtree).
2. If the current spot is empty (NULL), we've found the insertion point. Create a new node and place it here.
3. If the new value is less than the current node's value, we must go left. Recursively call insert on the left child.
4. If the new value is greater than the current node's value, we must go right. Recursively call insert on the right child.
5. If the value already exists, we'll simply do nothing to avoid duplicates.

This image shows the "before" and "after" of inserting the value 40 into a sample BST. Trace the path from the root (100) to see how the algorithm would find the correct spot as the right child of 30.

To see this logic explained with helpful diagrams, you can refer to the following reading.

The C Implementation

Translating this recursive logic to C involves a particularly elegant pattern. The insert function will return a pointer to the root of the tree it just modified. This allows us to "re-link" the subtrees as we return from the recursive calls.

Let's watch a detailed explanation of how to implement this in code. This video is one of the clearest explanations of the recursive insertion pattern.

The resulting C function, following this pattern, looks like this:

// Helper function to create a new node
struct node* createNode(int value) {
    struct node* newNode = malloc(sizeof(struct node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Recursive insert function
struct node* insert(struct node* root, int data) {
    // Base case: If the tree or subtree is empty, create and return a new node.
    if (root == NULL) {
        return createNode(data);
    }

    // Recursive step: Traverse the tree
    if (data < root->data) {
        // Go left, and link the returned subtree to the current node's left child.
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        // Go right, and link the returned subtree to the current node's right child.
        root->right = insert(root->right, data);
    }

    // If data is equal to root->data, we do nothing.
    // Finally, return the (possibly modified) root of the current subtree.
    return root;
}

3. The Search Operation

Searching a BST is simpler than inserting because we don't need to modify the tree's structure. The logic directly follows from the BST property, making it very efficient.

The Algorithm

1. Start at the root.
2. If the current spot is NULL, the value doesn't exist in the tree. The search fails.
3. If the search value matches the current node's value, you've found it! The search succeeds.
4. If the search value is less than the current node's value, recursively search the left subtree.
5. If the search value is greater than the current node's value, recursively search the right subtree.

At each step, we eliminate about half of the remaining tree, which is why this operation is so fast on a balanced tree.

4. A Complete C Program Walkthrough

Now that we've examined the insert and search algorithms separately, let's watch a complete, practical demonstration that puts everything together in a single C program.

5. Your Turn: Code and Practice

Here is a complete program that you can compile and run. It uses the struct node* insert(...) pattern we focused on. Read through the main function to see how the tree is built and then queried.

Try to predict the output before you run it. What will the tree look like after all the insertions?

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// The node structure
struct node {
    int data;
    struct node *left;
    struct node *right;
};

// Helper function to create a new node
struct node* createNode(int value) {
    struct node* newNode = malloc(sizeof(struct node));
    if (newNode != NULL) {
        newNode->data = value;
        newNode->left = NULL;
        newNode->right = NULL;
    }
    return newNode;
}

// Insert function using the recursive return-and-reassign pattern
struct node* insert(struct node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }

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

// Search function
bool search(struct node* root, int data) {
    // Base cases: root is null or data is present at root
    if (root == NULL) {
        return false;
    }
    if (root->data == data) {
        return true;
    }

    // Value is greater than root's data, so search in right subtree
    if (root->data < data) {
        return search(root->right, data);
    }

    // Value is smaller than root's data, so search in left subtree
    return search(root->left, data);
}

int main() {
    struct node *root = NULL;

    // Insert nodes into the BST
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);

    // Test the search function
    int value_to_find = 60;
    if (search(root, value_to_find)) {
        printf("%d was found in the tree.\n", value_to_find);
    } else {
        printf("%d was not found in the tree.\n", value_to_find);
    }

    value_to_find = 99;
    if (search(root, value_to_find)) {
        printf("%d was found in the tree.\n", value_to_find);
    } else {
        printf("%d was not found in the tree.\n", value_to_find);
    }

    // Remember to free the allocated memory in a real application!
    // (We will cover tree destruction in a later lesson)

    return 0;
}

Conclusion

In this lesson, we made the leap from theory to practice. You've seen how the logical, recursive rules of a Binary Search Tree are translated directly into C functions for insertion and searching.

Key Takeaways:

• BST operations like insert and search are most naturally implemented using recursion.
• The insert function uses a powerful pattern where it returns a node pointer, allowing the calling function to link the newly formed subtree back into the main tree (root->left = insert(...)).
• The search function efficiently traverses the tree, discarding half of the remaining nodes at each step, without modifying the tree structure.
• The entire tree is managed through a single root pointer, which points to the topmost node.

Preview of the Next Lesson:
Now that we can build a tree by inserting nodes, how can we visit and inspect every node within it? In our next lesson, we will implement the three fundamental tree traversal algorithms: in-order, pre-order, and post-order. You'll see how these traversals allow us to process or display the tree's data in different, useful sequences.