Please construct a binary search tree (BST) and implement a search function. The BST needs to be constructed according to the sequence of the input data. Your search function needs to achieve two purposes: the first is to confirm whether the target is found, and the second is to calculate the number of comparisons taken in total for the search procedure.
#include <iostream>
using namespace std;
class Nodes{
};
void setBST(){
}
void findElement(){
}
int main(){
// Read the basic input data
int num_input, target;
int input[1000];
cin >> num_input;
for(int i=0; i<num_input; i++){
cin >> input[i];
}
cin >> target;
//////////Hint//////////
// (1) Construct a binary search tree
// (2) Impliment the search function
// (3) According to the result of search function to print the answer
// note: You can use inorder traversal to check whether your BST is constructed correctly
return 0;
}
The first line of the input data is the total number of nodes in the BST.
The second line of input data is the sequence of node values.
The third line of input data is the target value to search for.
The first line of the output is to indicate whether the target is found. If so, print "found"; otherwise print "not found".
The second line of output is the total number of comparisons taken in this search.
note ***There is a new line at the end of each output***