C Program to Perform Searching in a BST

This is a C Program to perform searching an element in BST. To search a given key in Bianry Search Tree, we first compare it with root, if the key is present at root, we return root. If key is greater than root’s key, we recur for right subtree of root node. Otherwise we recur for left subtree.

Here is source code of the C Program to Perform Searching in a BST. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<stdio.h>
```
```
#include<stdlib.h>
```
```
 
```
```
struct node {
```
```
    int key;
```
```
    struct node *left, *right;
```
```
};
```
```
 
```

// A utility function to create a new BST node

```
struct node *newNode(int item) {
```

    struct node *temp = (struct node *) malloc(sizeof(struct node));

```
    temp->key = item;
```
```
    temp->left = temp->right = NULL;
```
```
    return temp;
```
```
}
```
```
 
```

// A utility function to do inorder traversal of BST

```
void inorder(struct node *root) {
```
```
    if (root != NULL) {
```
```
        inorder(root->left);
```
```
        printf("%d ", root->key);
```
```
        inorder(root->right);
```
```
    }
```
```
}
```
```
 
```

/* A utility function to insert a new node with given key in BST */

struct node* insert(struct node* node, int key) {

    /* If the tree is empty, return a new node */

```
    if (node == NULL)
```
```
        return newNode(key);
```
```
 
```

    /* Otherwise, recur down the tree */

```
    if (key < node->key)
```

        node->left = insert(node->left, key);

```
    else if (key > node->key)
```

        node->right = insert(node->right, key);

```
 
```

    /* return the (unchanged) node pointer */

```
    return node;
```
```
}
```
```
 
```

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

    // Base Cases: root is null or key is present at root

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

```
        return root;
```
```
 
```
```
    // Key is greater than root's key
```
```
    if (root->key < key)
```

        return search(root->right, key);

```
 
```
```
    // Key is smaller than root's key
```
```
    return search(root->left, key);
```
```
}
```
```
 
```

// Driver Program to test above functions

```
int main() {
```
```
    /* Let us create following BST
```
```
     50
```
```
     /     \
```
```
   30      70
```
```
     /  \    /  \
```
```
20   40  60   80 */
```
```
    struct node *root = NULL;
```
```
    root = insert(root, 50);
```
```
    insert(root, 30);
```
```
    insert(root, 20);
```
```
    insert(root, 40);
```
```
    insert(root, 70);
```
```
    insert(root, 60);
```
```
    insert(root, 80);
```
```
 
```

    // print inoder traversal of the BST

```
    printf("Inorder traversal: ");
```
```
    inorder(root);
```

    printf("\nThe key %d found at: %u",30, search(root, 30));

```
    return 0;
```
```
}
```

Output:

$ gcc SearchBST.c
$ ./a.out
 
Inorder traversal: 20 30 40 50 60 70 80 
The key 30 found at: 8530784

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Implement Splay Tree

» Next - C Program to Implement Segment Tree

Related Posts:

Recommended Articles: