title: Inserting elements from a sorted array into a BST in an efficient way
body: <p>I am struggling with this exercise:</p>
  <blockquote>
  <p>Given a BST T, whose nodes contain only a key field, a left and right field and a sorted array A which contains m keys. Write an efficient algorithm which inserts into T any A's keys which are not already present in T. You must not apply the <code>InsertBST(T,key)</code> algorithm on single A's keys.</p>
  </blockquote>
  <p>For example if the BST contains 1,3,4,5 and A contains 1,2,5,6, I have to insert 2,6 without using <code>InsertBST(T,2)</code> and <code>InsertBST(T,6)</code>.</p>
  <p>This is what I tried:</p>
  <pre><code>Algo(T,A,index)
       if T != null then
            Algo(T-&gt;sx,A,index)
            p = NewNode()
            p-&gt;key = A[index]
            if T-&gt;key &gt; A[index] then
                 T-&gt;sx = p
                 index = index + 1
            else if T-&gt;key &lt; A[index] then
                 T-&gt;dx = p
                 index = index + 1
            Algo(T-&gt;dx,A,index)
  </code></pre>
  <p>But it inserts nodes at the wrong places. Can you help me?</p>