当从 5 例如递归的权利，我们需要尽快停止处理单元，因为我们得到一个元素＆GT; 15 ，当我们将发生 20 。因此，我们通过 biggestSoFar 并停止处理元素，如果我们获得更大的价值。

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)

Given a preorder traversal, construct a binary tree. With recursion, it has to be deceptively simple :) but I just can't get it.

I see that the order of the arr has to be in the order nodes are inserted. What bugs me is:

How can the recursion insert nodes, in say the following preorder?

12, 10, 6, 13

15 is root, 5, 3 and left

How does 6 get inserted correctly as 10's left child?

    12
 10   13
6*

Here is the skeleton 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] < 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++);
}

EDIT:

I just realised, if I pass in the recursive call buildbst(root.left, arr+i, i++) is that the right way? Or am I approaching this all wrong - a mish-mash of dynamic programming and recursion and divide and conquer...

It can't already have a left / right child. You call it for the root, which has no children to start. Then you call it for the left child and create children where appropriate and call the function for those children and so on. You never visit the left child again once you go right and you can't get to a node from a function called on its child (since there is no connection up the tree, except the recursion stack).

This is what should happen when given 12, 10, 6, 13:

The above is not what will happen with your code for 2 reasons:

The below code should cover it.

node buildbst(int[] arr)
{
   node n = new node(arr[0]);
   // 9999999999 is meant to be > than the biggest element in your data
   buildbst(n, arr, 1, 9999999999);
   return node;
}

int buildbst(node current, int[] arr, int i, int biggestSoFar)
{
    if (i == arr.length) return i;

    // recurse left
    if (arr[i] < current.data)
    {
      current.left = new node(arr[i++]);
      i = buildbst(current.left, arr, i, current.data);
    }

    // recurse right
    if (i < arr.length && arr[i] < biggestSoFar)
    {
      current.right = new node(arr[i++]);
      i = buildbst(current.right, arr, i, biggestSoFar);
    }

    return i;
}

Explanation:

The purpose of biggestSoFar is to prevent:

    15                          15
   /                            /\
  5     versus (the correct)   5  20
 / \                          /
1   20                       1

When recursing left from 15 for example, we need to stop processing elements as soon as we get an element > 15, which will happen when we get 20. Thus we pass current.data and stop processing elements if we get a bigger value.

When recursing right from 5 for example, we need to stop processing elements as soon as we get an element > 15, which will happen when we get 20. Thus we pass biggestSoFar and stop processing elements if we get a bigger value.