Problem
Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.
Examples
Input: 1 2 3 4 5 6 7
Output:
4
/ \\
3 6
/ \\ / \\
3 4 6 7
Solutions
** Method 1 - Take the array’s middle element and insert it recursively**
- Pick up the middle element of the array
- Set it as the root
- Recursively build up left and right subtrees with lower and higher halves of the array
Here is the code in java:
public static BST sortedArrayToBST(int\[\] arr){
Node bst = new Node();
bst = sortedArrayToBST(arr, 0, arr.length-1, bst);
return bt;
}
private static Node sortedArrayToBST(int\[\] arr, int start, int end) {
if( start == end){
bst.insert(new Node(arr\[start\]));
return;
}
else if(start > end) {
return;
}
int middle = (start+end)/2;
Node node = new Node(arr\[middle\]);
//bst.insert(new Node(arr\[middle\]));
node.left = sortedArrayToBST(arr, start, middle - 1);
node.right = sortedArrayToBST(arr, middle+1, end);
return node;
}
Time complexity - O(n)
Space Complexity - O(1) (but if you internally think of recursion, it will be kind of O(n)