# C++ Program to Search for an Element in a Binary Search Tree

C++ Program to Search for an Element in a Binary Search Tree.

Problem Description

1. Implement binary search to find the existence of a search sequence in a binary search tree.
2. The worst case time complexity of Binary search is O(n) but for the average case, it is O(log(n)).

Problem Solution

1. Construct binary search tree for the given unsorted data array.
2. Search the element starting from the root of the tree.
3. Proceed with the search by comparing an element to the data of the node.
4. Exit.

Program/Source Code

C++ program to Search for an Element in a Binary Search Tree.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

```#include<iostream>

using namespace std;

// A structure representing a node of a tree.
struct node
{
int data;
node *left;
node *right;
};

// A function creating new node of the tree and assigning the data.
node* CreateNode(int data)
{
node *newnode = new node;
newnode->data = data;
newnode->left = NULL;
newnode->right = NULL;

return newnode;
}

// A function creating binary search tree.
node* InsertIntoTree(node* root, int data)
{
// Create node using data from argument list.
node *temp = CreateNode(data);
node *t = new node;
t = root;

// If root is null, assign it to the node created.
if(root == NULL)
root = temp;
else
{
// Find the position for the new node to be inserted.
while(t != NULL)
{
if(t->data < data )
{
if(t->right == NULL)
{
// If current node is NULL then insert the node.
t->right = temp;
break;
}
// Shift pointer to the left.
t = t->right;
}

else if(t->data > data)
{
if(t->left == NULL)
{
// If current node is NULL then insert the node.
t->left = temp;
break;
}
// Shift pointer to the left.
t = t->left;
}
}
}
return root;
}

// A function to search item in a BST.
void Search(node *root, int data)
{
int depth = 0;
node *temp = new node;
temp = root;
// Run the loop untill temp points to a NULL pointer.
while(temp != NULL)
{
depth++;
if(temp->data == data)
{
cout<<"\nData found at depth: "<<depth;
return;
}
// Shift pointer to left child.
else if(temp->data > data)
temp = temp->left;
// Shift pointer to right child.
else
temp = temp->right;
}

return;
}

int main()
{
char ch;
int n, i, a[20]={89, 53, 95, 1, 9, 67, 72, 66, 75, 77, 18, 24, 35, 90, 38, 41, 49, 81, 27, 97};
node *root = new node;
root = NULL;

// Construct the BST.
for(i = 0; i < 20; i++)
root = InsertIntoTree(root, a[i]);

up:
cout<<"\nEnter the Element to be searched: ";
cin>>n;

Search(root, n);

// Ask user to enter choice for further searching.
cout<<"\n\n\tDo you want to search more...enter choice(y/n)?";
cin>>ch;
if(ch == 'y' || ch == 'Y')
goto up;

return 0;
}```
Program Explanation

1. Construct binary search tree for the given unsorted data array by inserting data into tree one by one.
2. Take the input of data to be searched in the BST.
3. Starting from the root node, compare the data with data part of the node.
4. if data < temp->data, move the temp pointer to the left child.
5. if data > temp->data, move the temp pointer to the right child.
6. if data = temp->data, print the tree depth where it is found and return to main.
8. Ask user if he wants to search more if yes, repeat from 2.
9. Exit.

Runtime Test Cases
```Case 1:
Enter the Element to be searched: 35

Data found at depth: 7

Do you want to search more...enter choice(y/n)?y

Enter the Element to be searched: 41

Data found at depth: 9

Do you want to search more...enter choice(y/n)?y

Enter the Element to be searched: 9

Data found at depth: 4

Do you want to search more...enter choice(y/n)?y

Enter the Element to be searched: 2

Do you want to search more...enter choice(y/n)?n```

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

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