Given a sorted array, how do we create binary search which height balanced.
For example the array [1,2,3,4,5] must be transformed to the following binary tree
3
/
2 4
/
1 5
We can use the divide and conquer approach to solve this problem. To create a balanced tree, the number of nodes on the left sub-tree should be almost equal to that of right sub-tree.
How do we do it?
The create method is provided the lower and higher index parameters in addition to the actual array. We create the root node with the middle element and create the left and right sub trees with the left and right portions of the array.
Here is the C++ code.