title: algorithm - How to concatenate two binary search tree efficiently?
body: <p>I am <strong>not</strong> asking how to merge two binary search trees, as this question did <a href="https://stackoverflow.com/questions/1008513/how-to-merge-two-bsts-efficiently">How to merge two BST&#39;s efficiently?</a></p>
  
  <p>I am really asking how to <em>concatenate</em> two trees. So if tree A's all nodes are smaller than any node of tree B, we can concatenate two trees. But how do I do it efficiently?</p>
  
  <p>My idea is to find tree B's minimum, and then let tree A be the left child of minimum(tree B).</p>
  
  <p>This is simple enough and the time is <code>O(height of B)</code>.</p>
  
  <p>But I guess this solution has some problems:</p>
  
  <ol>
  <li>it may cause the final big tree not balanced any more </li>
  <li>What if the worst case running time is <code>O(h)</code>, where <code>h</code> is the max height of the two tree?</li>
  </ol>
  
  <p>Actually, The book "<a href="http://www.algorist.com/" rel="nofollow noreferrer">Algorithm Design Manual</a>" has this excise. Is my simple solution enough for this exercise?</p>
  
  <blockquote>
    <p>A concatenate operation takes two sets S1 and S2, where every key in S1 is smaller than any key in S2, and merges them together. <strong>Give an algorithm to concatenate two binary search trees into one binary search tree</strong>. The worst-case running time should be O(h), where h is the maximal height of the two trees.</p>
  </blockquote>
  
  <p>Thanks</p>