Bulding a Binary Search Tree recursively

Welcome to Programming Tutorial official website. Today - we are going to cover how to solve / find the solution of this error Bulding a Binary Search Tree recursively on this date .

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:

  1. if size is 0, return null.
  2. create a BST containing array[start] at the root.
  3. 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.)
  4. 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.
  5. 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.