Binary Search Trees in C++ – 2 : Occurrences function

We now look at a function which counts the number of occurrences of any particular data entry in a BST.

We first give a recursive version of the function.

——–

int occurrences ( Node *root, const Item& target)

//returns the # of occurrences of target in the BST rooted at root.

{

if (! root )

return 0;

if (root->data == target)

return 1 + occurrences(root->right, target) + occurrences (root->left, target);

else if (target< root->data)

return occurrences(root->left, target);

else

return occurrences (root->right, target);

}

————

In the non-recursive version of the occurrences function, we use a while loop to scan the relevant nodes. Each time we encounter target, we increment a variable count by 1.

—–

int occurrences ( Node *root, const Item& target)

{

int count = 0;

Node *temp = root;

while (true)

{

if (! temp)

break;

if (temp->data == target)

count ++;

else if (target < temp->data)

temp = temp->left;

else

temp = temp-> right;

}

return count;

}

————–

Counting the number of times an entry appears in a BST takes O(log n) time in the average case, and O(n) time in the worst case.

—————

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: