Binary Search Trees

Index

Binary Search Trees

A Binary Search Tree (BST) is a binary tree data structure with the following properties:

Value Ordering: Each node in the BST has a value, and the values in the left subtree of a node are less than the value of the node, while the values in the right subtree are greater than the value of the node.
Binary Tree Structure: Each node in the BST has at most two children, referred to as the left child and the right child.

The ordering property of BSTs makes searching, insertion, and deletion operations efficient, typically with average time complexity of O(log n), where n is the number of nodes in the tree. However, in the worst case, the time complexity can be O(n) if the tree becomes unbalanced.

Here’s a simple implementation of a Binary Search Tree in C:

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

// Define a structure for a binary tree node
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// Function to create a new binary tree node
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function to insert a new node into the binary search tree
struct TreeNode* insert(struct TreeNode* 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;
}

// Function to perform an in-order traversal of the binary tree (for testing)
void inOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

// Main function
int main() {
    struct TreeNode* root = NULL;

    // Insert elements into the binary search tree
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    // Print the elements of the binary search tree (in-order traversal)
    printf("In-order traversal of the binary search tree: ");
    inOrderTraversal(root);
    printf("\n");

    return 0;
}

Output:

In-order traversal of the binary search tree: 20 30 40 50 60 70 80

Code Explanation

1. Define the TreeNode Structure

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

A TreeNode structure is defined with three members:
- data: Stores the integer value of the node.
- left: A pointer to the left child node.
- right: A pointer to the right child node.

2. Function: createNode

struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Purpose: Creates a new binary tree node.
Parameters:
- data: The value to be stored in the node.
Steps:
1. Allocate memory for a new node.
2. Check if memory allocation fails. If it does, print an error message and exit.
3. Assign data to the data field of the new node.
4. Set left and right pointers to NULL.
5. Return the newly created node.

3. Function: insert

struct TreeNode* insert(struct TreeNode* 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;
}

Purpose: Inserts a new node into the binary search tree.
Parameters:
- root: The root of the BST.
- data: The value to be inserted.
Steps:
1. If the root is NULL, create a new node and return it.
2. If data is less than the data of the current node, recursively insert into the left subtree.
3. If data is greater than the data of the current node, recursively insert into the right subtree.
4. Return the root of the BST.

4. Function: inOrderTraversal

void inOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

Purpose: Performs an in-order traversal of the BST (left, root, right).
Parameters:
- root: The root of the BST.
Steps:
1. Recursively traverse the left subtree.
2. Print the data of the current node.
3. Recursively traverse the right subtree.

5. Main Function

int main() {
    struct TreeNode* root = NULL;
 
    // Insert elements into the binary search tree
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
 
    // Print the elements of the binary search tree (in-order traversal)
    printf("In-order traversal of the binary search tree: ");
    inOrderTraversal(root);
    printf("\n");
 
    return 0;
}

Steps:
1. Initialize the BST with root set to NULL.
2. Insert elements 50, 30, 20, 40, 70, 60, and 80 into the BST.
3. Perform an in-order traversal of the BST and print the elements.

Search for a value in BST

To search for a value in a Binary Search Tree (BST), you can traverse the tree starting from the root node and compare the value you are searching for with the values in each node. Here’s how you can implement the search algorithm in C:

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

// Define a structure for a binary tree node
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// Function to create a new binary tree node
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function to search for a value in the binary search tree
struct TreeNode* search(struct TreeNode* root, int value) {
    // If the tree is empty or the value is found at the root
    if (root == NULL || root->data == value) {
        return root;
    }
    // If the value is less than the root's data, search the left subtree
    if (value < root->data) {
        return search(root->left, value);
    }
    // If the value is greater than the root's data, search the right subtree
    return search(root->right, value);
}

// Main function
int main() {
    struct TreeNode* root = NULL;

    // Insert elements into the binary search tree
    root = createNode(50);
    root->left = createNode(30);
    root->right = createNode(70);
    root->left->left = createNode(20);
    root->left->right = createNode(40);
    root->right->left = createNode(60);
    root->right->right = createNode(80);

    // Search for values in the binary search tree
    int valueToSearch = 20;
    struct TreeNode* result = search(root, valueToSearch);
    if (result != NULL) {
        printf("Value %d found in the binary search tree.\n", valueToSearch);
    } else {
        printf("Value %d not found in the binary search tree.\n", valueToSearch);
    }

    // Free dynamically allocated memory
    free(root->left->left);
    free(root->left->right);
    free(root->left);
    free(root->right->left);
    free(root->right->right);
    free(root->right);
    free(root);

    return 0;
}

Output:

Value 20 found in the binary search tree.

Insert Node in BST

To insert a node into a Binary Search Tree (BST), you need to maintain the ordering property of the BST. Here’s how you can implement the insertion algorithm in C:

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

// Define a structure for a binary tree node
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// Function to create a new binary tree node
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function to insert a new node into the binary search tree
struct TreeNode* insert(struct TreeNode* root, int value) {
    // If the tree is empty, create a new node and return it
    if (root == NULL) {
        return createNode(value);
    }
    // Otherwise, recur down the tree
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    // Return the unchanged node pointer
    return root;
}

// Function to perform an in-order traversal of the binary tree (for testing)
void inOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

// Main function
int main() {
    struct TreeNode* root = NULL;

    // Insert elements into the binary search tree
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    // Print the elements of the binary search tree (in-order traversal)
    printf("In-order traversal of the binary search tree: ");
    inOrderTraversal(root);
    printf("\n");

    // Free dynamically allocated memory
    // Note: It's essential to implement proper memory deallocation logic in real-world scenarios
    free(root->left->left);
    free(root->left->right);
    free(root->left);
    free(root->right->left);
    free(root->right->right);
    free(root->right);
    free(root);

    return 0;
}

Output:

In-order traversal of the binary search tree: 20 30 40 50 60 70 80

Delete a Node in a BST

Deleting a node from a Binary Search Tree (BST) involves maintaining the ordering property of the tree while removing the node. There are three cases to consider when deleting a node from a BST:

Node to be deleted has no children (leaf node): In this case, simply remove the node from the tree.
Node to be deleted has one child: In this case, replace the node to be deleted with its child.
Node to be deleted has two children: In this case, find the inorder successor (or predecessor) of the node to be deleted, which is the smallest (or largest) node in its right (or left) subtree. Replace the node to be deleted with the inorder successor (or predecessor), and delete the inorder successor (or predecessor) from its original position.

Here’s the C code implementing the deletion operation in a BST:

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

// Define a structure for a binary tree node
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// Function to create a new binary tree node
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function to find the minimum value node in a binary tree
struct TreeNode* findMinNode(struct TreeNode* node) {
    struct TreeNode* current = node;
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}

// Function to delete a node from the binary search tree
struct TreeNode* deleteNode(struct TreeNode* root, int key) {
    if (root == NULL) {
        return root;
    }
    // If the key to be deleted is smaller than the root's key, go to the left subtree
    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    }
    // If the key to be deleted is greater than the root's key, go to the right subtree
    else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    }
    // If the key is the same as the root's key, then this is the node to be deleted
    else {
        // Node with only one child or no child
        if (root->left == NULL) {
            struct TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        // Node with two children: Get the inorder successor (smallest in the right subtree)
        struct TreeNode* temp = findMinNode(root->right);
        // Copy the inorder successor's content to this node
        root->data = temp->data;
        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

// Function to perform an in-order traversal of the binary tree (for testing)
void inOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

// Main function
int main() {
    struct TreeNode* root = createNode(50);
    root->left = createNode(30);
    root->right = createNode(70);
    root->left->left = createNode(20);
    root->left->right = createNode(40);
    root->right->left = createNode(60);
    root->right->right = createNode(80);

    printf("Binary search tree before deletion:\n");
    inOrderTraversal(root);
    printf("\n");

    // Delete node with value 30
    root = deleteNode(root, 30);

    printf("Binary search tree after deletion:\n");
    inOrderTraversal(root);
    printf("\n");

    // Clean up memory
    // (You may need to implement a separate function to deallocate memory properly)

    return 0;
}

Output:

Binary search tree before deletion:
20 30 40 50 60 70 80 
Binary search tree after deletion:
20 40 50 60 70 80

Time Complexity:

In a balanced BST:

Search Operation: Since the tree is balanced, the search operation has a time complexity of O(log n), where n is the number of nodes in the tree. This is because the height of a balanced BST is approximately logarithmic to the number of nodes.
Insertion and Deletion Operations: With balanced trees, insertion and deletion operations also have a time complexity of O(log n). Balancing operations may take additional time, but they are infrequent and amortized over multiple operations.

Binary Search Trees