__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.

Nevertheless once you have mastered the art of working there is no better way to make sure Forex Trading Software cost-effective protection. I spoke with one efficient Currency trading trader who described his working experience like having my very own personal money device.

ReplyDeleteNative Trader System is genuinely easy to use and it’s been tested for more than a year. People with virtually no trading experience and starting out with very little money are now making some VERY SERIOUS MONEY. THIS is no scam. And they’re not selling anything. You could be seeing HUGE profits on AUTOPILOT. Native Trader System is all you need! No more promises, pure profit only! Don’t miss your chance to become successful today with Native Trader System!

ReplyDeleteSuperior post, keep up with this exceptional work. It's nice to know that this topic is being also covered on this web site so cheers for taking the time to discuss this! Thanks again and again! BinaryStrategy.com

ReplyDelete