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 fields: 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

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
3[2] 5[1] 7[3] 9[2]

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
struct BinaryNode
BinaryNode* left;
BinaryNode* right;
int data;

BinaryNode* root;

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;
//Note: ALL insertions are as leaf nodes
BinaryNode* curr;
curr = root;
// Find the Node's parent
parent = curr;
if(t->data > curr->data)
curr = curr->right;
curr = curr->left;

if(t->data < parent->data)
parent->left = t;
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;

while(input >> temp){
cout<< temp << ", ";

cout << "Error opening file";

int ch,tmp1;
int level = 1;
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 : ";
case 1 : cout<<endl;
cout<<" In-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
case 2: cout << endl;
cout<<" Tree "<<endl;
cout<<" -------------------"<<endl;
case 3 : cout<<" Enter data to be deleted : ";
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:

 / \
3   9

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.

EDIT: Ah, reading your post more closely, we know this already. Sorry.

For each node, count and store the number of comparisons required when searching for the node

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.

This article has been dead for over six months. Start a new discussion instead.