C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Binary Search Tree — Searching for an Element in a Binary Search Tree

Searching for an Element in a Binary Search Tree

This is the operation that gives the BST its power: fast, ordered searching — typically in O(log n) time for balanced trees.

Binary Search Tree — Searching for an Element

Concept Overview

In a BST:

  • Left subtree → all values less than the node.
  • Right subtree → all values greater than the node.

So, to search for a given key:

  1. Compare the key with the root node’s value.
  2. If equal → element found.
  3. If smaller → search in left subtree.
  4. If greater → search in right subtree.
  5. Continue recursively or iteratively until the element is found or NULL is reached.

Algorithm (Recursive)

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

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

        return root;

 

    if (key < root->data)

        return search(root->left, key);

    else

        return search(root->right, key);

}

 

C Program: Binary Search Tree - Searching for an Element in a BST

C 
#include <stdio.h>


#include <stdlib.h>


 


// Structure for BST 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 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) {


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


        return root;


 


    if (key < root->data)


        return search(root->left, key);


    else


        return search(root->right, key);


}


 


// Inorder traversal for verification


void inorder(struct Node* root) {


    if (root != NULL) {


        inorder(root->left);


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


        inorder(root->right);


    }


}


 


int main() {


    struct Node* root = NULL;


    int key;


 


    // Construct 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");


 


    printf("Enter element to search: ");


    scanf("%d", &key);


 


    struct Node* result = search(root, key);


    if (result != NULL)


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


    else


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


 


    return 0;


}

Output

 
OUTPUT 1 :
Inorder Traversal of BST: 20 30 40 50 60 70 80
Enter element to search: 60
Element 60 found in the BST.

OUTPUT 2 :
Inorder Traversal of BST: 20 30 40 50 60 70 80
Enter element to search: 25
Element 25 not found in the BST.

Visualization

        50

       /  \

     30    70

    / \    / \

  20  40  60  80

  • Searching for 60 → compare (50 → right → 70 → left → 60 found).
  • Searching for 25 → compare (50 → left → 30 → left → 20 → not found).

Complexity Analysis

Case

Time Complexity

Space Complexity

Best Case

O(1)

O(1)

Average Case

O(log n)

O(log n) (recursive)

Worst Case (skewed)

O(n)

O(n)

For balanced BSTs, searching is very efficient — roughly log₂(n) comparisons.

Key Takeaways

  • BST search follows the divide-and-conquer principle.
  • Recursion mirrors the tree’s structure perfectly.
  • For performance-critical systems, an iterative version avoids recursion overhead.
  • Foundation for deletion and successor/predecessor algorithms.

 

Previous
Next