# 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