Kannon-den (Silver Pavilion) , Kyoto
Here is a problem that requires us to create a Binary Search Tree that is height balanced
Given a sorted array, convert it into a height-balanced binary search tree.
Understanding the problem
A height balanced tree has equal number of nodes or "off by one" number of nodes on either side of each subtree
Solving it
The problem states that the array is already sorted so it is quite easy to determine the "middle" of the tree. If the array has even number of elements we can pick the middle of the array and round up or down to get the root of the tree
After we get the root of the tree, we can assign the left and right sides of the tree by generalizing and repeating the process for the sub-arrays on the left and right of the middle element. This is a recursive solution
And here is the recursive algorithm -
function createNode (array)
if (array.length == 0)
return null;
node = array's middle element
node.left = createNode(left sub array)
node.right = createNode(right sub array)
return node