C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Binary Search Tree (BST) — Search Operation

 Concept Overview

A Binary Search Tree (BST) maintains elements in a sorted structure, making searching much faster than in a normal binary tree.

The property of BST:

  • Left subtree → contains nodes less than the parent.
  • Right subtree → contains nodes greater than the parent.

 Search Logic

To search for a key (target value):

  1. Start from the root node.
  2. If the key == root->data, element found.
  3. If the key < root->data, search in the left subtree.
  4. If the key > root->data, search in the right subtree.
  5. If you reach a NULL node, the key is not present.

C Program: Binary Search Tree (BST) — Search Operation

Method 1: Recursive BST Search

C 
#include <stdio.h>


#include <stdlib.h>


 


// Define the structure for a node


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));


    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;


}


 


// Recursive function to search a key in BST


struct Node* search(struct Node* root, int key) {


    // Base cases: root is NULL or key is present at root


    if (root == NULL || root->data == key)


        return root;


 


    // Key is greater than root's key


    if (key > root->data)


        return search(root->right, key);


 


    // Key is smaller than root's key


    return search(root->left, key);


}


 


// Inorder traversal to verify structure


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;


    struct Node* result;


 


    // Insert nodes into BST


    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 BST: ");


    inorder(root);


    printf("\n");


 


    int key = 60;


    result = search(root, key);


    if (result != NULL)


        printf("Key %d found in BST.\n", key);


    else


        printf("Key %d not found in BST.\n", key);


 


    key = 25;


    result = search(root, key);


    if (result != NULL)


        printf("Key %d found in BST.\n", key);


    else


        printf("Key %d not found in BST.\n", key);


 


    return 0;


}

Output

 
OUTPUT :
Inorder Traversal of BST: 20 30 40 50 60 70 80
Key 60 found in BST.
Key 25 not found in BST.

Tree Structure

After insertion, BST looks like:

        50

       /  \

     30    70

    / \    / \

  20  40  60  80

  • Searching 60 → Found
  • Searching 25 → Not found

 

C Program: Binary Search Tree (BST) — Search Operation

Method 2: Iterative BST Search (Without Recursion)

Here’s an iterative version, useful when you want to avoid recursive stack overhead.

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* 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;


}


 


// Iterative Search Function


struct Node* searchIterative(struct Node* root, int key) {


    while (root != NULL) {


        if (key == root->data)


            return root;


        else if (key < root->data)


            root = root->left;


        else


            root = root->right;


    }


    return NULL;


}


 


void inorder(struct Node* root) {


    if (root) {


        inorder(root->left);


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


        inorder(root->right);


    }


}


 


int main() {


    struct Node* root = NULL;


    struct Node* result;


 


    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 BST: ");


    inorder(root);


    printf("\n");


 


    int key = 40;


    result = searchIterative(root, key);


    if (result != NULL)


        printf("Key %d found in BST.\n", key);


    else


        printf("Key %d not found in BST.\n", key);


 


    key = 100;


    result = searchIterative(root, key);


    if (result != NULL)


        printf("Key %d found in BST.\n", key);


    else


        printf("Key %d not found in BST.\n", key);


 


    return 0;


}

Output

 
OUTPUT :
Inorder Traversal of BST: 20 30 40 50 60 70 80
Key 40 found in BST.
Key 100 not found in BST.

Complexity Analysis

Operation

Average Case

Worst Case (Skewed Tree)

Search

O(log n)

O(n)

Space (Recursive)

O(h)

O(n)

Space (Iterative)

O(1)

O(1)

Key Points

  • BST search works efficiently when the tree is balanced.
  • For unbalanced trees, performance can degrade to O(n).
  • Self-balancing BSTs like AVL Tree and Red-Black Tree overcome this problem.

 

Previous
Next