How to recursively insert elements into a binary tree and keep it balanced java?

Question

I am doing a project for class and am stuck on trying to develop this method. Would anyone be able to give me an example? The instructions for the method are below. Thanks!

The method insertBalanced is a BST method which receives an array of elements in sorted order from the client. It is recursive and will require a helper method to pass the array to the recursive method along with lowest and highest indexes (lo and hi). The strategy for the method is as follows: if lo <= hi then there is at least one element in the range. Calculate the middle, mid, between lo and hi, similar to the binary search approach, and call insert(array[mid]). As demonstrated in class, the order of insertions will be to always insert the middle element of the range we’re given. So you will recurse left of the mid element and right of the mid element. The sample code below would construct the tree shown below.

Answer 1

Would anyone be able to give me an example?

Let the input be the array {1, 4, 5, 8, 10, 11}

Then perform these steps:

• If the array is empty, return null
• Otherwise, take the middle element of the array. We will take 5 (it could also be 8 since the array size is even).
• Create a node n with this value
• Use recursion to create a binary tree for the array at the left of this value, so for {1, 4}. We receive a node reference from this recursion.
• Make the left child of n to be the node we get from the previous step
• Use recursion to create a binary tree for the array at the right of this value, so for {8, 10, 11}. We receive a node reference from this recursion.
• Make the right child of n to be the node we get from the previous step
• Finally, return the node n.

I will not present the code for this, as this is the code challenge for you to do.

Answer 2

Presumably, before this assignment, you worked with code that could insert an element into a proper position in a BST. For this assignment, you want to do this:

• Divide the array into three parts:
• • A middle element
• • A sub-array with elements to the left of, i.e., with lower value than, the middle element
• • a sub-array with elements to the right of, i.e., with greater value than, the middle element
• Insert the middle element, the same as in an earlier assignment.
• Use recursion to handle the left and the right sub-arrays

I would suggest a method with a header that resembles this:

public BSTNode (Comparable [] arr, int first, int last)

Where arr is the array of elements to be inserted, first is the start of the sub-array, and last is the end of the sub-array. Returns null when there is no element to be inserted. There is a pre-condition that arr must be sorted in ascending order.