Binary Search Tree key/value pair - I know the value but not the key C++

Question

I have a simple question that I am confused about. I know what is the concept of having a key/value pair in a Binary Search Tree and how the tree looks like when it is built.

What I am unsure is of how to search for a value in such a BST if I have no track of what its key would be?

For example:

Let say I have a binary search tree full of integers (as values) and also unique integers (as keys). And let say I want to count the number of times a specific integer (lets say: 200) occurs in this BST. So what I know, 200 is the "value" and not the "key". Hence I dont know the key at all.

How can I search now for all the "200"s in the whole BST? Does it become a simple BST now and I dont need the key at all? But again, the tree is arranged to the left child and the right child using the "key" and not the value.

I can also give you a code sample of how I initialize the BST:

void insertNode(TreeNode *&p, int key, int value)
{
  if (p == NULL) {
    p = new TreeNode;
    p->key = key;
    p->value = value;
    p->left = NULL;
    p->right = NULL;
    return;
  }

  if (key < p->key)
    insertNode(p->left, key, value);
  else
    insertNode(p->right, key, value);
}

Any help would be appreciated.

Answer 1

You can not take advantage of the fact that the tree is binary search tree if you want to search by value instead of key. So you have no other option but to iterate over the whole tree using BFS for instance.

Answer 2

Binary search tree(BST) is very useful for storing data for rapid access, storage, and deletion. Data in a binary search tree are stored in tree nodes, and must have associated with them an ordinal value or key; these keys are used to structure the tree such that the value of a left child node is less than that of the parent node, and the value of a right child node is greater than that of the parent node. Sometimes, the key and datum are one and the same.

Typical key values include simple integers or strings, the actual data for the key will depend on the application. Lets consider a binary search tree that stores string/double pairs. That is, the key is the string value and the data associated with the key is a double value. Developers can search the tree using string values.

In this case, a basic recursive search algorithm will look like:

 node search (node, key) {
   if node is null then return null;

   if node.key = key then
      return node

   if key < node then
      return search (node.left, key);
   else
      return search (node.right, key);
  }   

where the params are node: root of the tree & key: the value to be searched.

So typically we can search based on the required key but not on the associated value with the key.