二进制搜索树 - 实现“搜索”功能

我正在尝试实现二进制搜索树，但“搜索”函数为除根之外的每个条目返回错误的值 .

该函数应返回其值与key参数匹配的节点的地址，如果该节点不存在，则返回NULL .

#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;
}

当我运行代码时，我得到以下内容：

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

我知道每个节点的“左”和“右”指针都正确链接，因为“delAll”函数成功删除了所有节点 .

将“cout”语句添加到“search”函数会显示该函数似乎返回正确的地址 . 为什么从main调用时会打印错误的地址？