C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Binary Search Tree Insertion

Binary Search Tree (BST)

 Concept Overview

A Binary Search Tree (BST) is a special kind of binary tree that maintains a sorted order of elements.

Each node satisfies:

  • All values in the left subtree are less than the node’s key.
  • All values in the right subtree are greater than the node’s key.

This property allows efficient searching, insertion, and deletion (on average O(log n)).

 Insertion Logic

To insert a new node into a BST:

  1. Start from the root.
  2. If the new key is less than the root’s key → go left.
  3. If the new key is greater than the root’s key → go right.
  4. Repeat until you find an empty spot (NULL), and insert the new node there.

 

C Program: Binary Search Tree Insertion

Method 1: BST Insertion (Recursive Approach)

C 
#include <stdio.h>


#include <stdlib.h>


 


// Define the structure for a node in BST


struct Node {


    int data;


    struct Node *left, *right;


};


 


// Function to create a new node


struct Node* createNode(int value) {


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


    if (newNode == NULL) {


        printf("Memory allocation failed!\n");


        exit(1);


    }


    newNode->data = value;


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


    return newNode;


}


 


// Function to insert a node in BST (Recursive)


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


    // If tree is empty, return new node


    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 unchanged root pointer


    return root;


}


 


// Inorder Traversal (to verify BST)


void inorder(struct Node* root) {


    if (root != NULL) {


        inorder(root->left);


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


        inorder(root->right);


    }


}


 


// Main Function


int main() {


    struct Node* root = NULL;


 


    // Insert nodes


    root = insert(root, 50);


    root = insert(root, 30);


    root = insert(root, 70);


    root = insert(root, 20);


    root = insert(root, 40);


    root = insert(root, 60);


    root = insert(root, 80);


 


    printf("Inorder Traversal of the BST: ");


    inorder(root);


    printf("\n");


 


    return 0;


}

Output

 
OUTPUT :
Inorder Traversal of the BST: 20 30 40 50 60 70 80

Step-by-Step Example

Inserting elements:
50, 30, 70, 20, 40, 60, 80

BST structure after insertion:

        50

       /  \

     30    70

    / \    / \

  20  40  60  80

Inorder traversal of BST always gives a sorted order:

20 30 40 50 60 70 80

 

C Program: Binary Search Tree Insertion

Method 2: Iterative Insertion (Alternative Approach)

Here’s an iterative version — avoids recursion and is useful for large trees.

C 
#include <stdio.h>


#include <stdlib.h>


 


struct Node {


    int data;


    struct Node *left, *right;


};


 


struct Node* createNode(int value) {


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


    newNode->data = value;


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


    return newNode;


}


 


struct Node* insertIterative(struct Node* root, int value) {


    struct Node* newNode = createNode(value);


    struct Node* parent = NULL;


    struct Node* current = root;


 


    while (current != NULL) {


        parent = current;


        if (value < current->data)


            current = current->left;


        else if (value > current->data)


            current = current->right;


        else


            return root; // Duplicate keys not allowed


    }


 


    if (parent == NULL)


        root = newNode;


    else if (value < parent->data)


        parent->left = newNode;


    else


        parent->right = newNode;


 


    return root;


}


 


void inorder(struct Node* root) {


    if (root) {


        inorder(root->left);


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


        inorder(root->right);


    }


}


 


int main() {


    struct Node* root = NULL;


 


    root = insertIterative(root, 50);


    root = insertIterative(root, 30);


    root = insertIterative(root, 70);


    root = insertIterative(root, 20);


    root = insertIterative(root, 40);


    root = insertIterative(root, 60);


    root = insertIterative(root, 80);


 


    printf("Inorder Traversal of BST: ");


    inorder(root);


    printf("\n");


 


    return 0;


}

Output

 
OUTPUT :
Inorder Traversal of the BST: 20 30 40 50 60 70 80

Complexity Analysis

Operation

Average Case

Worst Case

Insertion

O(log n)

O(n) (skewed tree)

Search

O(log n)

O(n)

Deletion

O(log n)

O(n)

Space

O(n)

O(n)

 

Previous
Next