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

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

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

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.

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;

`}`

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”.

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 find any mistake above, kindly email to [email protected]**

**Related Posts:**

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