Binary Search Tree (BST) in C

In the previous lesson, you learned about trees and binary trees.

Now we study a very important special type of binary tree called a Binary Search Tree.

BSTs make searching operations very fast and efficient.

What Is a Binary Search Tree?

A Binary Search Tree is a binary tree that follows a specific rule:

• Left subtree contains values less than the node
• Right subtree contains values greater than the node

This rule is applied recursively to every node.

Why Use a BST?

BSTs allow:

• Fast searching
• Efficient insertion
• Ordered data storage

They perform much better than linear structures for large data.

BST Node Structure

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

Creating a New Node

struct Node* createNode(int value) {
    struct Node* newNode =
        (struct Node*)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

Inserting a Node in BST

Insertion follows the BST property strictly.

struct Node* insert(struct Node* root, int value) {
    if (root == NULL)
        return createNode(value);

    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;
}

Example BST Creation

struct Node* root = NULL;

root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);

This creates a BST where values are stored in sorted order logically.

Searching in a BST

Searching becomes efficient due to ordering.

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

    if (root->data == key)
        return 1;

    if (key < root->data)
        return search(root->left, key);

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

Real-World Analogy

Think of a dictionary:

• Words are stored in sorted order
• You skip half the pages each time

BST works the same way.

Advantages of BST

• Fast searching
• Logical ordering
• Efficient insert and delete

Mini Practice

• Create a BST with 5 values
• Search for an element
• Print whether it exists or not

Quick Quiz

Q1. What rule does BST follow?

Left smaller, right greater

Q2. Is BST a binary tree?

Yes

Q3. Why is searching fast in BST?

Because data is ordered

Q4. Which side stores smaller values?

Left subtree

Q5. Is recursion used in BST operations?

Yes