# Binary Search Tree - implementing a "search" function

I'm trying to implement a Binary Search Tree, but the "search" function returns the wrong value for every entry except the root.

The function should return the address of the node whose value matches the key parameter or NULL if the node doesn't exist.

```
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct TreeNode {
string data;
TreeNode* left;
TreeNode* right;
TreeNode* parent;
};
int main()
{
TreeNode* search(TreeNode* root, string key);
TreeNode* insert(TreeNode* root, TreeNode* parent, string key);
void delAll(TreeNode* root);
vector<string> vals{"yo", "check", "boy", "hope", "this", "doesn't", "break"};
TreeNode* root = NULL;
// Build tree
for (auto key : vals)
{
root = insert(root, NULL, key);
}
cout << endl;
// Search for all keys
for (auto key: vals)
{
cout << key << " found at " << search(root, key) << endl;
}
delAll(root);
return 0;
}
void delAll(TreeNode* root)
{
if (root == NULL)
return;
delAll(root->left);
TreeNode* next = root->right;
delete root;
delAll(next);
}
TreeNode* search(TreeNode* root, string key)
{
if (root == NULL)
return NULL;
if (root->data == key)
return root;
if (key < root->data)
search(root->left, key);
else
search(root->right, key);
}
TreeNode* insert(TreeNode* root, TreeNode* parent, string key)
{
if (!root)
{
root = new TreeNode;
root->data = key;
root->left = NULL;
root->right = NULL;
root->parent = parent;
cout << "Added \"" << key << "\" at " << root << endl;
}
else if (key > root->data)
root->right = insert(root->right, root, key);
else
root->left = insert(root->left, root, key);
return root;
}
```

When I run the code, I get the following:

```
Added "yo" at 0x5574f9b94f60
Added "check" at 0x5574f9b953b0
Added "boy" at 0x5574f9b953f0
Added "hope" at 0x5574f9b95430
Added "this" at 0x5574f9b95470
Added "doesn't" at 0x5574f9b954b0
Added "break" at 0x5574f9b954f0
yo found at 0x5574f9b94f60
check found at 0x7ffe97caf730
boy found at 0x7ffe97caf730
hope found at 0x7ffe97caf730
this found at 0x7ffe97caf730
doesn't found at 0x7ffe97caf730
break found at 0x7ffe97caf730
```

I know the "left" and "right" pointers of each node are linked correctly because the "delAll" function successfully deletes all the nodes.

Adding "cout" statements to the "search" function shows that the function seemingly returns the correct address. Why does the wrong address get printed when called from main?

### 1 Answer

You almost had it. Since search is recursive if must return its result.

```
TreeNode* search(TreeNode* root, string key)
{
if (root == NULL)
return NULL;
if (root->data == key)
return root;
if (key < root->data)
return search(root->left, key); // return this value
else
return search(root->right, key); // return this value
return NULL; // never hit
}
```

Matthew Fisher
posted this

## Have an answer?

JD