title: Build BST from Preorder
body: <p>Like many newbies, my head blows up from recursion. I looked up a lot of answers/explanations on SO. but I am still unclear on the concept. (This is not homework, I am trying to relearn what I unlearned and recursion was never a string point)</p>
  
  <p>Given a preorder traversal, construct a binary tree. With recursion, it has to be deceptively simple :) but I just can't get it.</p>
  
  <p>I <em>see</em> that the order of the arr has to be in the order nodes are inserted. What bugs me is:</p>
  
  <ol>
  <li>What if the node already has a left/right? How does this work?</li>
  <li><p>How can the recursion insert nodes, in say the following preorder?</p>
  
  <pre><code>12, 10, 6, 13
  </code></pre></li>
  </ol>
  
  <p>15 is root, 5, 3 and left</p>
  
  <p>How does 6 get inserted correctly as 10's left child?</p>
  
  <pre><code>    12
   10   13
  6*
  </code></pre>
  
  <p>Here is the skeleton code:</p>
  
  <pre><code>main()
  {
     int[] arr = {};
     //make the first node a root node.
     node n = new node(arr[0]);
     buildbst(n, arr, 0)
  }
  
  buildbst(node root, int[] arr, int i)
  {
     if (i == arr.length) return;
  
     if (arr[i] &lt; root.data)
        root.left = new node (arr[i]);
     else
        root.right = new node(arr[i]);
  
     buildbst(root.left, arr, i++);
     buildbst(root.right, arr, i++);
  }
  </code></pre>
  
  <p>EDIT:</p>
  
  <p>I just realised, if I pass in the recursive call <code>buildbst(root.left, arr+i, i++)</code>
  is that the right way? Or am I approaching this all wrong - a mish-mash of dynamic programming and recursion and divide and conquer...</p>