# Bulding a Binary Search Tree recursively

I am having problems understanding where to start writing this method. The method builds a tree using data gotten from an array (which is a global variable). The method takes two parameters which are ints, size and start.

I have already written the insert and delete methods recursively but I cannot figure out how to even start thinking about building this. Not sure what size and start are supposed to do, and when the node is added, how would I go about moving to the next index in the array without including it as a parameter.

An algorithm or any help would be greatly appreciated. Thanks!

Edit: I am not able to use the insert and delete methods when building the tree. The build has to be its own. And the array only stores the preorder values to be put into the tree

## Answer

My guess is that `size`

and `start`

are parameters that allow the calling code to build a binary search tree from a sub-array of the global data array. If this is a class assignment, you should confirm this with your teacher.

If my guess is correct, it’s fairly simply to write the method by building on the work you’ve already done. Create an empty binary tree, then beginning at offset `start`

in the global data array, insert consecutive elements until you’ve inserted `size`

of them.

You don’t need the array as a parameter since it’s a global variable.

Edit (based on edit to question):

If the global array is already in preorder, then it’s structure will be:

index: start start+1 end (see below) start+size +--------------+--------------------------+-------------------------+ | array[start] | ... smaller elements ... | ... larger elements ... | +--------------+--------------------------+-------------------------+

Each section after `array[start]`

will also have the same structure.

To build a BST from this, the first element goes into the root of the search tree. Then all following elements that are smaller than the first element go into the left subtree and the first larger element through to the end of the array go into the right subtree. So the algorithm would be:

- if
`size`

is 0, return`null`

. - create a BST containing
`array[start]`

at the root. - scan from
`start+1`

to the end of the array for the index of the first element greater than the element at`start`

. Call this index`end`

. (If all remaining elements are smaller than the element at index`start`

, then`end`

will be the array length.) - set the left subtree of the binary search tree created in step 2 to be the result of recursively calling the method with arguments
`end - start - 1`

for the new size and`start+1`

for the new start. - set the right subtree of the binary search tree to be the result of recursively calling the method with arguments
`start + size - end`

for the new size and`end`

for the new start.