C Program to Search an Element in a Tree Recursively

This is a C Program to search an element in a Binary Search Tree recursively.

Problem Description

We have to write a C program to search an element(node) in a Binary Search Tree recursively.

Expected Input and Output

Case 1. Balanced Tree:When the weight is equal on both the sides of root.

If the input tree is              
                    25
                  /    \  
                 17     35   
                / \     / \ 
              13  19   27 55 
and the key to be searched for is 15,
then the output will be : Key not found.

Case 2. Right Skewed Tree:When the nodes at every level just have a right child.

If the input tree is
                    1   
                     \
                      2    
                       \    
                        3 
                         \
                          4
                           \
                            5
and the key to be searched for is 4,
then the output will be : Key found in tree.

Case 3. Tree having just one node

If the input tree is
                15
and the key to be searched for is 15,
then the output will be : Key found in tree.

Problem Solution

We can easily find the element in a BST if it exists.
1. If the key is greater than the root node of the tree, it will lie in right subtree.
2. If it key is smaller than the root node of the tree, it will lie in the left subtree.

Subscribe Now: Data Structures in C Newsletter | Important Subjects Newsletters

Program/Source Code

Here is source code of the C Program for searching a node or an element in a Binary Search Tree. The program is successfully compiled and tested using Codeblocks gnu/GCC compiler on windows 10. The program output is also shown below.

```
/*
```

 * C Program to search an element in a Binary Search Tree

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

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

```
    newnode->info = key;
```
```
    newnode->left = NULL;
```
```
    newnode->right = NULL;
```
```
    return(newnode);
```
```
}
```
```
int search(struct node *head, int key)
```
```
{
```
```
    while (head != NULL)
```
```
    {
```
```
        if (key > head->info)
```
```
        {
```

            return search(head->right, key);

```
        }
```
```
        else if (key < head->info)
```
```
        {
```

            return search(head->left, key);

```
        }
```
```
        else
```
```
        {
```
```
            return 1;
```
```
        }
```
```
    }
```
```
    return 0;
```
```
}
```
```
/*
```
```
 * Main Function
```
```
 */
```
```
int main()
```
```
{
```
```
    int flag = 0;
```
```
    /* Creating first Tree. */
```

    struct node *newnode = createnode(25);

```
    newnode->left = createnode(17);
```
```
    newnode->right = createnode(35);
```

    newnode->left->left = createnode(13);

    newnode->left->right = createnode(19);

    newnode->right->left = createnode(27);

    newnode->right->right = createnode(55);

```
    /* Sample Tree 1:
```
```
     *               25
```
```
     *             /    \
```
```
     *            17     35
```
```
     *           / \     / \
```
```
     *         13  19   27 55
```
```
     */
```
```
    flag = search(newnode,15);
```
```
    if (flag)
```
```
    {
```

        printf("Key %d found in tree 1 \n", 15);

```
    }
```
```
    else
```
```
    {
```

        printf("Key %d not found in tree 1\n", 15);

```
    }
```
```
 
```
```
    /* Creating second Tree. */
```
```
    struct node *node = createnode(1);
```
```
    node->right = createnode(2);
```
```
    node->right->right = createnode(3);
```

    node->right->right->right = createnode(4);

    node->right->right->right->right = createnode(5);

    /* Sample Tree 2:   Right Skewed Tree (Unbalanced).

```
     *               1
```
```
     *                \
```
```
     *                 2
```
```
     *                  \
```
```
     *                   3
```
```
     *                    \
```
```
     *                     4
```
```
     *                      \
```
```
     *                       5
```
```
     */
```
```
    flag = search(node,4);
```
```
    if (flag)
```
```
    {
```

        printf("Key %d found in tree 2\n", 4);

```
    }
```
```
    else
```
```
    {
```

        printf("Key %d not found in tree 2\n", 4);

```
    }
```
```
 
```
```
    /* Creating third Tree. */
```
```
    struct node *root = createnode(15);
```

    /* Sample Tree 3- Tree having just one root node.

```
     *              15
```
```
     */
```
```
    flag = search(root,15);
```
```
    if (flag)
```
```
    {
```

        printf("Key %d found in tree 3 \n", 15);

```
    }
```
```
    else
```
```
    {
```

       	printf("Key %d not found in tree 3\n", 15);

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

Program Explanation

1. Here in the above program we have written a function search(struct node *head, int key), which is taking in two parameters the root node of tree and the key which is to be searched in tree.
2. In order to search for an element in a BST we compare it with each and every node in tree so that we can decide whether to follow the left or the right child of that node.
3. We start with the root node, we compare the key with the root node i.e. head of the tree, if the key is less than the root node, we start searching in left subtree i.e we compare the key with the left child of root node, and so on.
4. Similarly if the key is greater than the root node, we start searching in right subtree i.e. we compare key with the right child of root node and so on recursively.
5. If we are able to find the element we print “Key found in tree” else we print “Key not found”.

Runtime Test Cases

Key 15 not found in tree 1
Key 4 found in tree 2
Key 15 found in tree 3

Sanfoundry Global Education & Learning Series – 1000 C Programs.

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

If you wish to look at other example programs on Trees, go to Trees. If you wish to look at programming examples on all topics, go to C Programming Examples.

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

« Prev - C Program to Print All Nodes of Linked List using Recursion

» Next - C Program to Implement a Heap and Perform Heap Operations

Related Posts:

Practice Programming MCQs
Check Programming Books
Practice Computer Science MCQs
Check Data Structure Books
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: