Minimal Tree
problem
Given a sorted(increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.
How to solve
This minimal tree means creating height balanced tree. Firstly, we want the root to be the middle of the array, since this would mean that half the elements would be less than the root and half would be greater than it. We proceed with constructing our tree in a similar fashion. The middle of each subsection of the array becomes the root of the node. The left half of the array will become our left subtree, an the right half of the array will become the right subtree. We do this in recursively we create a height balanced tree in O(N).
- Insert into the tree the middle element of the array.
- Insert (into the left subtree) the left subarray elements.
- Insert (into the right subtree) the right subarray elements.
- Recurse.
