This exercise should take about 20 minutes.

So here we go: given a sorted array of numbers for example [1,3,5,8, 120], or [1,2,3,4,5,6], make a balanced binary tree. A balanced tree is one where the minimum depth and the maximum depth do not have a difference greater than one, or in other words where no "branches" are deeper than any other branches by one level. A binary tree is one in which each node has 0, 1 or 2 children. Unlike in this picture, our binary tree will be organized in such a way that the left child of each node will be greater than its parent, and the right child will be greater, making it useful for purposes of searching.

For the purposes of this exercise we'll be using javascript, as its more bare bones than ruby and syntactically closer to bare metal languages, you could easily however implement this in ruby as well. Of note is the fact that this algorithm cannot exceed O(n) time as we must iterate over the entire original array. An optimal solution then will have O(n) time.

Lets think through a solution: The first parameter to consider is our input, which is a sorted list. By default we want our root to be the middle value of this sorted list, since this way we can just grab a value to right to be the first child, and a value to the left to be the second. Not just any value, because we want the children of the children to follow the same pattern as the root we want to grab the middle of the list. Essentially we'll split the list in half with and then split the list in half again... does this smell like recursion? It does! So we'll make a node creation queue recursively, and then just go through it and make the nodes. Seems simple enough.

Now here's the code that makes the magic happen:

Not so bad is it? The bottom line, as long as you think through an algorithm, you can figure out a simple solution to the problem!

## No comments:

## Post a Comment