Convert Sorted Array to BST


import org.apache.commons.lang3.builder.ToStringBuilder;

/**
 * Convert a sorted array into a Binary Search Tree
 *
 */
public class TreeUtils {

    static class Tree {
        int val;
        Tree left;
        Tree right;

        Tree(int x) {
            val = x;
        }
        @Override
        public String toString() {
            return ToStringBuilder.reflectionToString(this);
        }
    }

    public static void main(String[] args) {
        int num[] = {1, 2, 3, 4, 5, 6, 7};
        Tree tree = sortedArrayToBST(num, 0, num.length - 1);
        System.out.println(tree);
    }

    public static Tree sortedArrayToBST(int[] num, int start, int end) {
        if (start > end)
            return null;
        int middle= (start + end) / 2;
        Tree root = new Tree(num[middle]);
        root.left = sortedArrayToBST(num, start, middle - 1);
        root.right = sortedArrayToBST(num, middle + 1, end);
        return root;
    }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s