Binary Search Tree (BST) Operations in C

Introduction to Binary Search Tree (BST) Program

           A Binary Search Tree (BST) is a node-based binary tree data structure that maintains the following properties:

  1. Left Subtree: All nodes in the left subtree of a node contain values less than the node’s value.

  2. Right Subtree: All nodes in the right subtree of a node contain values greater than the node’s value.

  3. No Duplicate Nodes: Typically, BSTs do not contain duplicate values.

BSTs are widely used for efficient searching, insertion, and deletion operations, with an average time complexity of O(log n) for these operations, where n is the number of nodes.

This program will demonstrate how to:

  1. Create a BST by inserting nodes.

  2. Search for a value in the BST.

  3. Traverse the BST using in-order traversal (which prints nodes in ascending order).

Program Structure

  1. Node Structure: Each node contains:

    • data: The value stored in the node.

    • left: Pointer to the left child.

    • right: Pointer to the right child.

  2. Functions:

    • createNode(value): Creates a new node.

    • insert(root, value): Inserts a value into the BST.

    • search(root, value): Searches for a value in the BST.

    • inOrderTraversal(root): Traverses the BST in in-order.

Steps to Implement :

download code

 

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

// Define the structure of the BST node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

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

// Function to insert a new node in BST
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;
}

// Function for inorder traversal (Left-Root-Right)
void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

// Function to search for a value in the BST and print its location
int search(struct Node* root, int value) {
    if (root == NULL) {
        return 0; // Value not found
    }
    if (root->data == value) {
        printf("%d is found at the root.\n", value);
        return 1; // Value found at root
    }
    if (value < root->data) {
        if (search(root->left, value)) {
            printf("%d is found in the left subtree of %d.\n", value, root->data);
            return 1;
        }
    } else {
        if (search(root->right, value)) {
            printf("%d is found in the right subtree of %d.\n", value, root->data);
            return 1;
        }
    }
    return 0; // Value not found
}

int main() {
    struct Node* root = NULL;
    int values[] = {50, 30, 70, 20, 40, 60, 80};
    int n = sizeof(values) / sizeof(values[0]);

    // Inserting values into BST
    for (int i = 0; i < n; i++) {
        root = insert(root, values[i]);
    }

    // Display the inorder traversal of the BST
    printf("Inorder Traversal of BST: ");
    inorderTraversal(root);
    printf("\n");

    // Search for a value in the BST
    int searchValue;
    printf("Enter a value to search in the BST: ");
    scanf("%d", &searchValue);

    if (!search(root, searchValue)) {
        printf("%d is not found in the BST.\n", searchValue);
    }

    return 0;
}

 

Understanding the code

struct Node {
    int data;           // Stores the value of the node
    struct Node* left;  // Pointer to the left child node
    struct Node* right; // Pointer to the right child node
};

In the above code : 

  1. int data;

    • This is the data field of the node.

    • It stores the integer value associated with the node.

    • For example, if the node represents the value 50, then data = 50.

  2. struct Node* left;

    • This is a pointer to the left child of the current node.

    • In a BST, the left child node contains a value less than the current node’s value.

    • If there is no left child, this pointer will be NULL.

  3. struct Node* right;

    • This is a pointer to the right child of the current node.

    • In a BST, the right child node contains a value greater than the current node’s value.

    • If there is no right child, this pointer will be NULL.

  

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory for the new node
    newNode->data = value; // Set the data field of the node
    newNode->left = newNode->right = NULL; // Initialize left and right pointers to NULL
    return newNode; // Return the newly created node
}

 

In the above code : 

The createNode function is responsible for dynamically creating a new node for a Binary Search Tree (BST). 

  1. Function Signature:

     struct Node* createNode(int value)
     

    • The function is named createNode.

    • It takes an integer value as input, which will be stored in the new node.

    • It returns a pointer to the newly created node (struct Node*).

  2. Memory Allocation:

     
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    • malloc is used to dynamically allocate memory for the new node.

    • sizeof(struct Node) calculates the size of the Node structure in bytes.

    • (struct Node*) is a typecast to ensure the pointer returned by malloc is of type struct Node*.

    • newNode is a pointer to the newly allocated memory block.

  3. Set the Data Field:

     
    newNode->data = value;

    • The data field of the new node is assigned the input value.

    • For example, if value = 50, then newNode->data = 50.

  4. Initialize Left and Right Pointers:

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

    • The left and right pointers of the new node are initialized to NULL.

    • This indicates that the new node has no children (it is a leaf node initially).

  5. Return the New Node:

     
    return newNode;

    • The function returns the pointer to the newly created node.

    • This allows the calling function to use the new node (e.g., to insert it into the BST).

 
struct Node* insert(struct Node* root, int value) {
    if (root == NULL) {
        return createNode(value); // Create a new node if the tree is empty
    }
    if (value < root->data) {
        root->left = insert(root->left, value); // Insert in the left subtree
    } else if (value > root->data) {
        root->right = insert(root->right, value); // Insert in the right subtree
    }
    return root; // Return the (possibly updated) root of the tree
}

 In above code : 

         The insert function is used to insert a new node with a given value into a Binary Search Tree (BST). It ensures that the BST property is maintained:

  • All values in the left subtree of a node are less than the node’s value.

  • All values in the right subtree of a node are greater than the node’s value.

  1. Function Signature:

     
    struct Node* insert(struct Node* root, int value)

    • The function is named insert.

    • It takes two arguments:

      • root: A pointer to the root of the BST (or subtree).

      • value: The integer value to be inserted into the BST.

    • It returns a pointer to the root of the BST (or subtree) after insertion.

  2. Base Case:

     
    if (root == NULL) {
    return createNode(value);
}

    • If the current root is NULL, it means the tree is empty (or we’ve reached a leaf node’s child position).

    • In this case, a new node is created using the createNode function, and the pointer to this new node is returned.

  3. Recursive Case:

     
    if (value < root->data) {
    root->left = insert(root->left, value); // Insert in the left subtree
} else if (value > root->data) {
    root->right = insert(root->right, value); // Insert in the right subtree
}

    • If the value is less than the current node’s data (root->data), the function recursively inserts the value into the left subtree.

    • If the value is greater than the current node’s data, the function recursively inserts the value into the right subtree.

    • The recursive calls ensure that the value is inserted at the correct position to maintain the BST property.

  4. Return the Root:

     
    return root;

    • After inserting the value (if necessary), the function returns the root of the current subtree.

    • This ensures that the tree structure is preserved and updated correctly.

 
void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);  // Traverse the left subtree
        printf("%d ", root->data);    // Visit the root node
        inorderTraversal(root->right); // Traverse the right subtree
    }
}

 In above code : 

         The inorderTraversal function is used to traverse a Binary Search Tree (BST) in in-order fashion. In-order traversal visits the nodes in the following order:

  1. Left Subtree: Traverse the left subtree.

  2. Root Node: Visit the root node.

  3. Right Subtree: Traverse the right subtree.

For a BST, in-order traversal prints the nodes in ascending order.

  1. Function Signature:

     
    void inorderTraversal(struct Node* root)

    • The function is named inorderTraversal.

    • It takes a single argument: root, which is a pointer to the root of the BST (or subtree).

    • It does not return any value (void).

  2. Base Case:

     
    if (root != NULL) {

    • If the current node (root) is NULL, the function stops and returns. This is the base case for the recursion.

    • If the node is not NULL, the function proceeds to traverse the tree.

  3. Traverse the Left Subtree:

     
    inorderTraversal(root->left);

    • The function recursively calls itself on the left child of the current node.

    • This ensures that all nodes in the left subtree are visited before the current node.

  4. Visit the Root Node:

     
    printf("%d ", root->data);

    • The value of the current node (root->data) is printed.

    • This is the “visit” step in the in-order traversal.

  5. Traverse the Right Subtree:

     
    inorderTraversal(root->right);

    • The function recursively calls itself on the right child of the current node.

    • This ensures that all nodes in the right subtree are visited after the current node.

 
int search(struct Node* root, int value) {
    if (root == NULL) {
        return 0; // Value not found
    }
    if (root->data == value) {
        printf("%d is found at the root.\n", value);
        return 1; // Value found at root
    }
    if (value < root->data) {
        if (search(root->left, value)) {
            printf("%d is found in the left subtree of %d.\n", value, root->data);
            return 1;
        }
    } else {
        if (search(root->right, value)) {
            printf("%d is found in the right subtree of %d.\n", value, root->data);
            return 1;
        }
    }
    return 0; // Value not found
}

 In above code : 

The search function is used to search for a value in a Binary Search Tree (BST) and print its location if found. It leverages the BST property to efficiently locate the value and provides information about where the value is found (e.g., at the root, in the left subtree, or in the right subtree).  

  1. Function Signature:

     
    int search(struct Node* root, int value)

    • The function is named search.

    • It takes two arguments:

      • root: A pointer to the root of the BST (or subtree).

      • value: The integer value to search for in the BST.

    • It returns an integer:

      • 1 if the value is found.

      • 0 if the value is not found.

  2. Base Case:

     
    if (root == NULL) {
    return 0; // Value not found
}

    • If the current node (root) is NULL, it means the value is not found in the tree (or subtree), so the function returns 0.

  3. Value Found at Root:

     
    if (root->data == value) {
    printf("%d is found at the root.\n", value);
    return 1; // Value found at root
}

    • If the current node’s data (root->data) matches the search value, the function prints that the value is found at the root and returns 1.

  4. Search in the Left Subtree:

     
    if (value < root->data) {
    if (search(root->left, value)) {
        printf("%d is found in the left subtree of %d.\n", value, root->data);
        return 1;
    }
}

    • If the search value is less than the current node’s data, the function recursively searches the left subtree.

    • If the value is found in the left subtree, it prints the location (e.g., “found in the left subtree of <parent>“) and returns 1.

  5. Search in the Right Subtree:

     
    else {
    if (search(root->right, value)) {
        printf("%d is found in the right subtree of %d.\n", value, root->data);
        return 1;
    }
}

    • If the search value is greater than the current node’s data, the function recursively searches the right subtree.

    • If the value is found in the right subtree, it prints the location (e.g., “found in the right subtree of <parent>“) and returns 1.

  6. Value Not Found:

     
    return 0; // Value not found

    • If the value is not found in the tree, the function returns 0.

 

The main function is the entry point of the program. It demonstrates how to:

  1. Create a BST by inserting values.

  2. Traverse the BST using in-order traversal.

  3. Search for a value in the BST.

Let’s break down the code step by step:

 
int main() {
    struct Node* root = NULL; // Initialize the root of the BST as NULL
    int values[] = {50, 30, 70, 20, 40, 60, 80}; // Array of values to insert into the BST
    int n = sizeof(values) / sizeof(values[0]); // Calculate the number of values in the array

    // Inserting values into BST
    for (int i = 0; i < n; i++) {
        root = insert(root, values[i]); // Insert each value into the BST
    }

    // Display the inorder traversal of the BST
    printf("Inorder Traversal of BST: ");
    inorderTraversal(root); // Perform in-order traversal
    printf("\n");

    // Search for a value in the BST
    int searchValue;
    printf("Enter a value to search in the BST: ");
    scanf("%d", &searchValue); // Read the value to search

    if (!search(root, searchValue)) {
        printf("%d is not found in the BST.\n", searchValue); // Print if the value is not found
    }

    return 0; // End of program
}

and finally in the main function in above code  

  1. Initialize the BST:

    c
    Copy
    struct Node* root = NULL;

    • The root pointer is initialized to NULL, indicating that the BST is initially empty.

  2. Array of Values:

    c
    Copy
    int values[] = {50, 30, 70, 20, 40, 60, 80};
int n = sizeof(values) / sizeof(values[0]);

    • An array values is defined, containing the values to be inserted into the BST.

    • The variable n is calculated as the number of elements in the values array.

  3. Insert Values into the BST:

    c
    Copy
    for (int i = 0; i < n; i++) {
    root = insert(root, values[i]);
}

    • A for loop is used to insert each value from the values array into the BST.

    • The insert function is called for each value, and the root of the BST is updated.

  4. In-Order Traversal:

    c
    Copy
    printf("Inorder Traversal of BST: ");
inorderTraversal(root);
printf("\n");

    • The inorderTraversal function is called to traverse the BST in in-order (left-root-right) and print the nodes in ascending order.

    • The result is displayed as: Inorder Traversal of BST: 20 30 40 50 60 70 80.

  5. Search for a Value:

    c
    Copy
    int searchValue;
printf("Enter a value to search in the BST: ");
scanf("%d", &searchValue);

    • The user is prompted to enter a value to search for in the BST.

    • The value is stored in the variable searchValue.

  6. Perform the Search:

    c
    Copy
    if (!search(root, searchValue)) {
    printf("%d is not found in the BST.\n", searchValue);
}

    • The search function is called to search for the value in the BST.

    • If the value is not found (search returns 0), a message is printed: <value> is not found in the BST.

  7. End of Program:

    c
    Copy
    return 0;

    • The program ends by returning 0, indicating successful execution.

Table of Contents
Binary tree traversals
BST Counting Nodes
Piyu's CS

Computer Science Education

Contact Us

info@piyuscs.com