title: Binary Search Tree - implementing a "search" function
body: <p>I'm trying to implement a Binary Search Tree, but the "search" function returns the wrong value for every entry except the root.</p>
  
  <p>The function should return the address of the node whose value matches the key parameter or NULL if the node doesn't exist.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;string&gt;
  #include &lt;vector&gt;
  
  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&lt;string&gt; vals{"yo", "check", "boy", "hope", "this", "doesn't", "break"};
      TreeNode* root = NULL;
  
      // Build tree
      for (auto key : vals)
      {
          root = insert(root, NULL, key);
      }
  
      cout &lt;&lt; endl;
  
      // Search for all keys
      for (auto key: vals)
      {
          cout &lt;&lt; key &lt;&lt; " found at " &lt;&lt; search(root, key) &lt;&lt;  endl;
      }
  
      delAll(root);
  
      return 0;
  }
  void delAll(TreeNode* root)
  {
      if (root == NULL)
          return;
  
      delAll(root-&gt;left);
      TreeNode* next = root-&gt;right;
  
      delete root;
  
      delAll(next);
   }
  TreeNode* search(TreeNode* root, string key)
  {
      if (root == NULL)
          return NULL;
      if (root-&gt;data == key)
          return root;
  
      if (key &lt; root-&gt;data)
          search(root-&gt;left, key);
      else
          search(root-&gt;right, key);
  }
  TreeNode* insert(TreeNode* root, TreeNode* parent, string key)
  {
  
      if (!root)
      {
          root = new TreeNode;
          root-&gt;data = key;
          root-&gt;left = NULL;
          root-&gt;right = NULL;
          root-&gt;parent = parent;
          cout &lt;&lt; "Added \"" &lt;&lt; key &lt;&lt; "\" at " &lt;&lt; root &lt;&lt; endl;
      }
      else if (key &gt; root-&gt;data)
          root-&gt;right = insert(root-&gt;right, root, key);
      else
          root-&gt;left = insert(root-&gt;left, root, key);    
  
      return root;
  }
  </code></pre>
  
  <p>When I run the code, I get the following:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>I know the "left" and "right" pointers of each node are linked correctly because the "delAll" function successfully deletes all the nodes.</p>
  
  <p>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?</p>