### Searching for a target key in a Binary Search Tree

Data values are given which we call a key and a binary search tree. To search for the key in the given binary search tree, start with the root node and compare the key with the data value of the root node. If they match, return the root pointer. If the key is less than the data value of the root node, repeat the process by using the left subtree. Otherwise, repeat the same process with the right subtree until either a match is found or the subtree under consideration becomes an empty tree.

```#include <stdio.h>
#include <stdlib.h>
struct tnode {
int data;
struct tnode *lchild, *rchild;
};
/* A function to serch for a given data value in a binary search tree*/
struct tnode *search(struct tnode *p, int key) {
struct tnode *temp;
temp = p;
while (temp != NULL) {
if (temp->data == key)
return (temp);
else if (temp->data > key)
temp = temp->lchild;
else
temp = temp->rchild;
}
return (NULL);
}

/*an iterative function to print the binary tree in inorder*/
void inorder1(struct tnode *p) {
struct tnode *stack;
int top;
top = -1;
if (p != NULL) {
top++;
stack[top] = p;
p = p->lchild;
while (top >= 0) {
while (p != NULL)/* push the left child onto stack*/
{
top++;
stack[top] = p;
p = p->lchild;
}
p = stack[top];
top--;
printf("%d\t", p->data);
p = p->rchild;

if (p != NULL) /* push right child*/
{
top++;
stack[top] = p;
p = p->lchild;
}

}
}
}
/* A function to insert a new node in binary search tree to
get a tree created*/
struct tnode *insert(struct tnode *p, int val) {
struct tnode *temp1, *temp2;
if (p == NULL) {
p = (struct tnode *) malloc(sizeof(struct tnode));
/* insert the new node as root node*/
if (p == NULL) {
printf("Cannot allocate\n");
exit(0);
}
p->data = val;
p->lchild = p->rchild = NULL;
} else {
temp1 = p;
/* traverse the tree to get a pointer to that
node whose child will be the newly created node*/
while (temp1 != NULL) {
temp2 = temp1;
if (temp1->data > val)
temp1 = temp1->lchild;
else
temp1 = temp1->rchild;
}
if (temp2->data > val) {
temp2->lchild = (struct tnode*) malloc(sizeof(struct tnode));
/*inserts the newly created node
as left child*/
temp2 = temp2->lchild;
if (temp2 == NULL) {
printf("Cannot allocate\n");
exit(0);
}
temp2->data = val;
temp2->lchild = temp2->rchild = NULL;
} else {
temp2->rchild = (struct tnode*) malloc(sizeof(struct tnode));
/*inserts the newly created node
as left child*/
temp2 = temp2->rchild;
if (temp2 == NULL) {
printf("Cannot allocate\n");
exit(0);
}
temp2->data = val;
temp2->lchild = temp2->rchild = NULL;
}
}
return (p);
}
int main() {
struct tnode *root = NULL, *temp = NULL;
int n, x;
printf("Enter the number of nodes in the tree\n");
scanf("%d", &n);
while (n -- > 0)
{
printf("Enter the data value\n");
scanf("%d", &x);
root = insert(root, x);
}
printf("The created tree is :\n");
inorder1(root);
printf("\n Enter the value of the node to be searched\n");
scanf("%d", &n);
temp = search(root, n);
if (temp != NULL)
printf("The data value is present in the tree \n");
else
printf("The data value is not present in the tree \n");
getchar();
return 0;
}
```

#### Explanation

Input: 1. The number of nodes that the tree to be created should have
2. The data values of each node in the tree to be created
3. The key value

Output: If the key is present and appears in the created tree, then a message
“The data value is present in the tree” appears. Otherwise the message
“The data value is not present in the tree” appears.

#### Example

Input: 1. The number of nodes that the created tree should have = 5
2. The data values of the nodes in the tree to be created are: 10, 20, 5, 9, 8
3. The key value = 9

Output: The data is present in the tree