title: Binary Search Tree - Copying a tree
body: <p>I'm messing around with sorting data structures in C++ so I'm writing a bunch of functions to make a binary search tree class. I'm a bit lost when trying to create a copy constructor/function to copy a tree.</p>
  
  <pre><code>void BST&lt;T&gt;::copyBST(Node* treeOriginal, Node* treeNew){
  
          if (treeOriginal == NULL) //base case to end recursion when at tree end
              treeNew == NULL;
          else{
              Node* treeNew = new Node;  //create the node and set the new key to original
              treeNew-&gt;key = treeOriginal-&gt;key;
  
              Node* leftChild = new Node; //create a left node to be child of new node
              treeNew-&gt;left = leftChild;
              leftChild-&gt;parent = treeNew;
  
              Node* rightChild = new Node; //create a right node
              treeNew-&gt;right = rightChild;
              rightChild-&gt;parent = treeNew;
  
              copyBST(treeOriginal-&gt;left, leftChild); //call copy function on subtree of left child
              copyBST(treeOriginal-&gt;right, rightChild); //call copy function on subtree of right child
          } 
  }
  </code></pre>
  
  <p>Now a few things happen when I try run this. First, it doesn't copy all of the nodes, and will copy a different amount each time. This is strange to me since I'm calling a recursion on every node, since I start at the root and then call it on the left and right. I tried writing out the process on paper, visually planning out how it would copy the original tree but to me it seems like a logical process and can't find where it could get lost.</p>
  
  <p>I also added cout statements in the function to print out the original node's key, address, parent, and children, as well as the copy node's key, address, parent and children. The only problem I found in this test was that the copy node's parent address was always 00000000, or NULL. So apparently the piece of code </p>
  
  <pre><code>leftChild-&gt;parent = treeNew; and rightChild-&gt;parent = treeNew;
  </code></pre>
  
  <p>doesn't actually set the node's parent pointer to the parent. </p>
  
  <p>These were the only clear issues I could find while trying to fix this. I'm not sure how else to look for the problem. If you can't see any problems in the logic of the code, does anyone have any other ideas of how to find where the problem lies?</p>
  
  <p>Thank you!</p>