title: Node insertion binary tree C++
body: <p>I believe i implemented inserting a new node into a binary search tree, however my testing script shows my tree as being in valid</p>
  
  <p>My code where the value is inserted into the tree if there is no current node. </p>
  
  <pre><code>bool InsertRecursive(BinaryTreeNode* tree_node, int value) {
  
   if (tree_node == NULL)
   {
  
  BinaryTreeNode * pNode = new BinaryTreeNode;
  pNode-&gt;data = value;   // inserting node in
  pNode-&gt;left_child = NULL;
  pNode-&gt;right_child = NULL;
  tree_node = pNode ; 
  return true;
   }
         if(tree_node-&gt;data == value )   // if value already exists return false
  {
   return false ; 
    }
     else if (tree_node-&gt;data &gt; value)   // traverses to find the location for the value
      return InsertRecursive(tree_node-&gt;right_child, value);
    else 
  return InsertRecursive(tree_node-&gt;left_child, value);
  
   }
  </code></pre>
  
  <p>the actual method of inserting the node inside </p>
  
  <pre><code> bool BinaryTree::Insert(int value) {
  
  if (InsertRecursive(head, value)) {
  return true;
  } else
    return false;
  }
  </code></pre>
  
  <p>What my testing script says</p>
  
  <p>|   Test: Insert</p>
  
  <p><strong>|   |   -Should be a valid tree of size 1 after inserting '4'</strong></p>
  
  <p>|   |   |   You built an invalid tree. Why would you do that to me?</p>
  
  <p><strong>|   |   -Should be a valid tree of size 2 after inserting '2'</strong></p>
  
  <p>|   |   |   You built an invalid tree. Your code needs to get it's life together</p>
  
  <p>|   |   -Should be a valid tree of size 3 after inserting '3'</p>
  
  <p>|   |   |   <strong>You built an invalid tree. More coffee maybe?</strong></p>
  
  <p>|   |   -Insert(1) should return false for: [ d2-1 d1-2 d2-3 d0-4 d2-5 d1-6 d2-7 </p>
  
  <p>]
  <strong>|   |   |   It returned true. Unlike a boss</strong>
  |   Failed!</p>
  
  <p>So the problem should be with in where i actually insert the node as the tree is being read as in valid.  I am lost on how to solve this however and would like some guidance.</p>