I have to write a program that creates a binary search tree from a file and output it and several other requirements. One requirement that I cannot figure out is how to find the search cost for each node. These are the instructions I was given
Calculate the search cost for each node when it is inserted
– A binary node element has at least two data ﬁelds: Key and SearchCost
– For each node, count and store the number of comparisons required when searching for the
node (i.e., the number of comparisons = the search cost for the node = 1+ the depth of the
node)

And the output is supposed to be:

Input data: 5, 3, 9, 7
Create a binary search tree:
Key = 5 SearchCost = 1
Key = 3 SearchCost = 2
Key = 9 SearchCost = 2
Key = 7 SearchCost = 3
Total number of nodes is 4
To generate output on the screen we use the in-order traversal. Here each node is represented as
Key[SearchCost]:
3 5 7 9

I can currently print the input in in-order transversal however I cannot for the life of me figure out how to calculate the search cost and I cannot figure out how to assign these values to the keys. This is part of my code currently:

``````class BinarySearchTree
{
private:
struct BinaryNode
{
BinaryNode* left;
BinaryNode* right;
int data;

};
BinaryNode* root;

public:
BinarySearchTree()
{
root = NULL;
}

bool isEmpty() const { return root==NULL; }
void print_inorder();
void inorder(BinaryNode*);
void insert(int);
void remove(int);
void printTree(BinaryNode*);
void print_Tree(int level);
void showtree(BinaryNode*, int level);
void tree_line(BinaryNode*, int level);
};

// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)
{
BinaryNode* t = new BinaryNode;
BinaryNode* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;

// is this a new tree?
if(isEmpty()) root = t;
else
{
//Note: ALL insertions are as leaf nodes
BinaryNode* curr;
curr = root;
// Find the Node's parent
while(curr)
{
parent = curr;
if(t->data > curr->data)
curr = curr->right;
else
curr = curr->left;
}

if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}

int main()
{
BinarySearchTree b;

int temp;
int count = 0;
ifstream input;

string fileName;
cout<< endl<< "This program will read data from a user desginated file and create a binary search tree based on the input data." <<endl;
cout << endl << "Please enter a file name: ";
cin >> fileName;
cout << "The input data from the file is: " << endl;
input.open(fileName.c_str());

if(input.is_open()){
while(input >> temp){
cout<< temp << ", ";
b.insert(temp);
count++;
}
input.close();
}

else{
cout << "Error opening file";
}

int ch,tmp1;
int level = 1;
while(1)
{
cout<<endl<<endl;
cout<<" Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. In-Order Traversal "<<endl;
cout<<" 2. Output Tree " <<endl;
cout<<" 3. Removal "<<endl;
cout<<" 4. Exit "<<endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1 : cout<<endl;
cout<<" In-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
b.print_inorder();
break;
case 2: cout << endl;
cout<<" Tree "<<endl;
cout<<" -------------------"<<endl;
b.print_Tree(level);
break;
case 3 : cout<<" Enter data to be deleted : ";
cin>>tmp1;
b.remove(tmp1);
break;
case 4 :
return 0;

}
}
}
``````

I have really been struggling with this and if anyone could help me I would really appreciate it!

It might help to visualize the constructed tree. For your example sequence [5, 3, 9, 7], I get:

``````  5
/ \
3   9
/
7
``````

I'm not aware of "binary search cost" as a standard term, but it appears to be the element's tree depth plus one. This makes sense; this is how many node traversals (including the root) you have to make to find the element.

I'd store this in another field in `BinaryNode`, and the easiest way to get it is to keep track of tree depth when you're inserting nodes. In `BinarySearchTree::insert`, insert the root node with depth 1; then, for every other node, assign its depth as 1 higher than its parent.