title: Union of Two Binary Search Trees
body: <p>I need some help figuring out how to merge two binary search trees. My idea/algorithm for this:</p>
  
  <p>1) Make a new, third Binary search tree to keep the union of the other  two trees.</p>
  
  <p>2) Go through the first tree, copying all of its successive elements into the newly created tree.</p>
  
  <p>3) Go through the second tree doing the same as above.</p>
  
  <p>I have an add function which takes care of repetitions and putting stuff into the tree, so that part is not an issue. My problem is I don't know how to go through each of the nodes and manipulate them individually. I was thinking traversing the tree with something like:</p>
  
  <pre><code>public void inOrderTraverseTree(Node focusNode) {
          if (focusNode != null) {
               preorderTraverseTree(focusNode.leftChild);
               //this is where I can do an operation on the node
               preorderTraverseTree(focusNode.rightChild);
  </code></pre>
  
  <p>I'd like to take each successive node and add it to my third binary tree. As far as I can see, that's impossible to implement with any variation of the function above. Is there another way to go about this? Does it need a completely different algorithm?</p>