How to Search in a Binary Search Tree (BST) in C

To search in a BST in C, start at the root node and compare the target value with the current node's value. If equal, return the node; if smaller, search the left subtree; if larger, search the right subtree, repeating until the value is found or the subtree is empty.

Syntax

The search function in a BST typically uses recursion or iteration. It takes a pointer to the root node and the value to search for. It returns a pointer to the node containing the value or NULL if not found.

• struct Node*: pointer to a tree node
• root: current node to check
• key: value to find
• Returns pointer to node or NULL

c

struct Node* searchBST(struct Node* root, int key) {
    if (root == NULL || root->data == key) {
        return root;
    }
    if (key < root->data) {
        return searchBST(root->left, key);
    } else {
        return searchBST(root->right, key);
    }
}

Example

This example creates a simple BST, then searches for a value and prints if it was found or not.

c

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

struct Node* insert(struct Node* root, int data) {
    if (root == NULL) return newNode(data);
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}

struct Node* searchBST(struct Node* root, int key) {
    if (root == NULL || root->data == key) {
        return root;
    }
    if (key < root->data) {
        return searchBST(root->left, key);
    } else {
        return searchBST(root->right, key);
    }
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    int key = 40;
    struct Node* result = searchBST(root, key);
    if (result != NULL) {
        printf("Value %d found in BST.\n", key);
    } else {
        printf("Value %d not found in BST.\n", key);
    }
    return 0;
}

Output

Value 40 found in BST.

Common Pitfalls

Common mistakes when searching in a BST include:

• Not checking if the current node is NULL before accessing its data, causing crashes.
• Confusing the comparison direction (searching left when key is greater).
• Not returning the result of recursive calls, leading to incorrect results.

Always ensure base cases are handled and recursion returns are used properly.

c

/* Wrong: Missing return in recursive calls */
struct Node* wrongSearch(struct Node* root, int key) {
    if (root == NULL || root->data == key) {
        return root;
    }
    if (key < root->data) {
        return wrongSearch(root->left, key); // Added missing return
    } else {
        return wrongSearch(root->right, key); // Added missing return
    }
}

/* Correct: Return recursive calls */
struct Node* correctSearch(struct Node* root, int key) {
    if (root == NULL || root->data == key) {
        return root;
    }
    if (key < root->data) {
        return correctSearch(root->left, key);
    } else {
        return correctSearch(root->right, key);
    }
}

Quick Reference

Tips for searching in a BST:

• Always start at the root node.
• Compare the key with current node's data.
• Go left if key is smaller, right if larger.
• Return node if found, or NULL if not.
• Use recursion or iteration consistently.

Key Takeaways

Search a BST by comparing the key with node data and moving left or right accordingly.

Always check for NULL nodes to avoid crashes during search.

Return the result of recursive calls to propagate the found node correctly.

Use recursion or iteration to implement the search clearly and simply.

If the search reaches a NULL node, the key is not in the BST.