Converting Array to a balanced BST(Binary Search Tree)

Question : 

Given an array you need to convert it into an balanced BST(Binary Search Tree).

Example :

Solution :

Given an array first step would be to sort it. You can probably use quick sort which will take average time O(NlogN) complexity. Once you have sorted you can apply following algorithm to convert it into a balance BST.

1. Get the Middle of the array and make it root.
2. Recursively do same for left half and right half.
   
   1. Get the middle of left half and make it left child of the root created in step 1.
   2. Get the middle of right half and make it right child of the root created in step 1.

TreeNode data structure

package Tree;

/**
 * Created by Aniket on 1/22/14.
 */
public class TreeNode {

    int data;
    TreeNode leftNode;
    TreeNode rightNode;

    public TreeNode(int data){
        this.data = data;
    }

    public TreeNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    public TreeNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }
}

 Code to transform a sorted array into balance BST.

package Tree;

import java.util.Arrays;

/**
 * Created by Aniket on 1/22/14.
 */
public class ArrayToBST {

    public static TreeNode convert(int[] ar, int start, int end){

        if(start > end)
            return null;

        int mid = start + ((end - start)/2);
        TreeNode root = new TreeNode(ar[mid]);
        root.setLeftNode(convert(ar,start,mid-1));
        root.setRightNode(convert(ar,mid+1,end));

        return root;

    }

    public static void main(String args[]){

        int array[] = new int[]{1,2,3,4,5,6,7};
        System.out.println("Array is : " + Arrays.toString(array));


        System.out.println("BST in pre order : ");
        PrintTree.printPreOrderTraversal(ArrayToBST.convert(array,0,array.length-1));

    }

}

and the output is

Array is : [1, 2, 3, 4, 5, 6, 7]
BST in pre order :
Data : 4
Data : 2
Data : 1
Data : 3
Data : 6
Data : 5
Data : 7


Pre-order traversal is a type of tree traversals. You can take a look at the types and code for each in the previous post on Tree traversal.