## Sunday, December 28, 2014

### Constructing a minimum height BST with elements from a sorted array.

Q. Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.

Algorithm:

1. Pass the array reference, starting index (s) and end index (e) recursively.
2. Calculate mid = (e+s)/2
3. Construct a new Node with array[mid] as the value.
4. Now node.left = (array, s, mid-1)
5. node.right = (array, mid+1, e)
6. Return this node.
7. Returning condition during recursion:
if(s > e) we must return null (no element to be placed there)
if(s==e) return new Node(array[s])

Source:

```public class Code{

public class Node{
int value;
Node left, right;
Node(){}
Node(int value){this.value = value;}
Node(int value, Node left, Node right){
this.value = value;
this.left = left;
this.right = right;
}
}

Node root;

void construct(int[] a){
root = build(a, 0, a.length-1);
}

Node build(int[] a, int s, int e){
if(s>e)return null;
else if(s==e)return new Node(a[s]);
else{
int mid = (e+s)/2;
Node node = new Node(a[mid]);
node.left = build(a, s, mid-1);
node.right = build(a, mid+1, e);
return node;
}
}

void printTree(){
inorder(root);
System.out.println("Balanced? : "+isBalanced()+" Height = "+checkB(root));
}

void inorder(Node node){
if(node==null)return;
inorder(node.left);
System.out.println(node.value);
inorder(node.right);
}

boolean isBalanced(){
return checkB(root)!=-1;
}

int checkB(Node node){
if(node == null)return 0;
int left = checkB(node.left)+1; if(left == 0)return -1;
int right = checkB(node.right)+1; if(right == 0)return -1;
int diff = Math.abs(left - right); if(diff > 1)return -1;
else return Math.max(left, right);
}

int height(Node node){
if(node == null)return 0;
int left = checkB(node.left)+1; if(left == 0)return -1;
int right = checkB(node.right)+1; if(right == 0)return -1;
return Math.max(left, right);
}

public static void main(String[] args){
Code tree = new Code();
int a[] = {3,4,2,1};
tree.construct(a);
tree.printTree();
}
}```

Output:

3
4
2
1
Balanced? : true Height = 3