title: Merging 2 Binary Search Trees
body: <p>How do you merge 2 Binary Search Trees in such a way that the resultant tree contains all the elements of both the trees and also maintains the BST property.</p>
  
  <p>I saw the solution provided in
  <a href="https://stackoverflow.com/questions/1008513/how-to-merge-two-bsts-efficiently">How to merge two BST&#39;s efficiently?</a></p>
  
  <p>However that solution involves converting into a Double Linked List. I was wondering if there is a more elegant way of doing this which could be done in place without the conversion. I came up with the following pseudocode. Does it work for all cases? Also I am having trouble with the 3rd case.</p>
  
  <pre><code>node* merge(node* head1, node* head2) {
          if (!head1)
              return head2;
          if (!head2)
              return head1;
  
          // Case 1.
          if (head1-&gt;info &gt; head2-&gt;info) {
              node* temp = head2-&gt;right;
              head2-&gt;right = NULL;
              head1-&gt;left = merge(head1-&gt;left, head2);
              head1 = merge(head1, temp);
              return head1;
          } else if (head1-&gt;info &lt; head2-&gt;info)  { // Case 2
              // Similar to case 1.
          } else { // Case 3
              // ...
          }
  }
  </code></pre>