__Problem__Create a balanced binary search tree from an array of

*n*elements.

__Solution__It's always easier to have an example to follow along with, so let the array below be our case study.

The first step is to sort the array. The next step is to load the tree with these elements. A simple way to do it is to use binary search with recursion, except that we're adding an element to the tree instead of 'searching' for it.

/**

* Create binary search tree.

*

**@param**array of elements *

*/**@return**The root of the tree.**public**Node makeTree(String[] array) {

**int**low = 0;

**int**high = array.length - 1;

**return**makeTree(low, high, array);

}

/**

* Create binary search tree.

*

**@param**low The lowest array position. *

**@param**high The highest array position. *

**@param**array of elements *

**@return**The root of the tree. */

**private**Node makeTree(

**int**low,

**int**high, String[] array) {

**if**(low > high) {

**return**

**null**;

}

**else**{

// Same as (low + high) / 2

**int**mid = (low + high) >>> 1;

Node node =

**new**Node(array[mid]); node.left = makeTree(low, (mid - 1), array);

node.right = makeTree((mid + 1), high, array);

**return**node;

}

}

The function recursively adds all the elements in the left subtree and then all the elements in the right subtree. Note that it works for edge cases where the input size is zero or one. The resulting balanced binary search tree is

Now the next question is, how do we check that the solution is correct? For this trivial example, we can verify it just by looking at the tree. We can see that every child on the left is less than its parent, and every child on the right is greater than its parent.

For a large input with hundreds or thousands of elements, it would be too time consuming to draw and visually verify the tree like we did above. The solution to this proceeding problem will be in a future blog post which will cover preorder, inorder, and postorder tree traversals.

For a large input with hundreds or thousands of elements, it would be too time consuming to draw and visually verify the tree like we did above. The solution to this proceeding problem will be in a future blog post which will cover preorder, inorder, and postorder tree traversals.

## No comments:

## Post a Comment