Binary Search Tree Program in C Using Recursion

A binary Search Tree is one of the most important and most asked data structures. So, before starting with the “Binary Search Tree Program in C Using Recursion“, it is very necessary to understand what is Binary Tree and Binary Search Tree.

What is Binary Tree and Binary Search Tree?

A binary Tree is a tree that has 0,1 or 2 child nodes only. In this tree, there are no specific ordering requirements for the values to be stored in the nodes. This tree is primarily concerned with the arrangement of nodes and their child relationships. Whereas, The binary search tree will insert the data by following the below rules:

1. Left child node data should be less than or equal to the root node.
2. Right child node data should be more than or equal to the root node.
3. In case of two same values, we have to follow one of the approaches that is, will insert all the equals data nodes to the left side or to the right side only.

Binary search tree program in c using recursion

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

// Basic structure for a binary tree 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 = NULL;
    newNode->right = NULL;
    return newNode;
}

// Then, Write a recursive C function to insert an element in a binary Search tree

struct Node* insertNode(struct Node* root, int value) {
    if (root == NULL) {
        return createNode(value);
    }
    if (value < root->data) {
        root->left = insertNode(root->left, value);
    } else if (value > root->data) {
        root->right = insertNode(root->right, value);
    }
    return root;
}
// Function to perform preorder traversal of the binary tree (root-left-right)

void preorderTraversal(struct Node* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data); // Print the current node's data
    preorderTraversal(root->left); // Recursively traverse the left subtree
    preorderTraversal(root->right); // Recursively traverse the right subtree
}

// Function to perform inorder traversal of the binary tree (left-root-right)
void inorderTraversal(struct Node* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left); // Recursively traverse the left subtree
    printf("%d ", root->data); // Print the current node's data
    inorderTraversal(root->right); // Recursively traverse the right subtree
}

// Function to perform postorder traversal of the binary tree (left-right-root)
void postorderTraversal(struct Node* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left); // Recursively traverse the left subtree
    postorderTraversal(root->right); // Recursively traverse the right subtree
    printf("%d ", root->data); // Print the current node's data
}


int main() {
    struct Node* root = NULL;
    
    // Inserting nodes into the binary search tree
    root = insertNode(root, 50);
    insertNode(root, 30);
    insertNode(root, 20);
    insertNode(root, 40);
    insertNode(root, 70);
    insertNode(root, 60);
    insertNode(root, 80);

Here, we write a recursive C Program for traversing a Binary tree in Preorder Inorder and postorder
   printf("Preorder Traversal: ");
    preorderTraversal(root);
    printf("\n");

    printf("Inorder Traversal: ");
    inorderTraversal(root);
    printf("\n");

    printf("Postorder Traversal: ");
    postorderTraversal(root);
    printf("\n");

    return 0;
    
    return 0;
}

Explanation of the above code:

1. First, we will include all the necessary header files like stdio.h for input/output operations and stdlib.h for dynamic memory allocation in the program.
2. Next, we will define a structure called Node to represent a node in the binary search tree. And each node contains an integer value (or any other type), as well as pointers to its left and right child nodes.
3. After this, we will make a createNode function which is defined to create a new node with the given value by the user. This function will allocate memory to the node, initializes its data and sets both left and right pointers to NULL. Then, this function will return a pointer to the newly created node.
4. Then, we will make another function insertNode. This function is defined to insert a new node into the binary search tree. Now, this function will take the root node of the tree and the value will be inserted in the node. So, if the root value is NULL, then we will make a new node and will set the given value and will return it to the createNode function.
5. So, in this function, if the tree is not empty, the function compares the value with the data in the current node. And if the value is less than the current node’s data, the function will recursively call the insertNode function for the left child of the current node. If the value is greater than the current node’s data, the function will recursively call the insertNode function for the right child.
6. Now, we will make an inorderTraversal function. In this function, we will perform an in-order traversal of the binary search tree. It takes the root node of the tree as a parameter and will recursively traverse the left subtree. And after that, it will visit the current node, and finally recursively traverses the right subtree. And, this function will visit the elements in ascending order.
7. In the main function, we start by initializing the root node of the binary search tree to NULL. After this, we will insert several nodes into the tree using the insertNode function. 

In the above code, we will insert the nodes with values 50, 30, 20, 40, 70, 60, and 80 in the order. After inserting the nodes, we call the inorderTraversal function to perform an inorder traversal of the tree and accordingly display the elements in sorted order.

Operations Performance:

Due to the efficient ordering property of the Binary Search Tree, the searching operation for a specific value can be done in O(log n) time complexity as an average time, where n is the number of nodes in the tree. And Insertion and deletion operations also have an average time complexity of O(log n).