Chapter4Q3.java

package crackingthecodinginterview;

/**
 * Created by ayberk on 4/30/14.
 *
 * 43 Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height
 */

import datastructures.*;

public class Chapter4Q3
{
    private static final int SIZE = 1024;

    public static void main(String[] args)
    {

        int[] arr = new int[SIZE];
        for (int i = 0; i < SIZE; i++) {
            arr[i] = i;
        }

        BinarySearchTree balancedTree = solve(arr);

        System.out.println(balancedTree.height()); // should be lg(SIZE) + 1 (assuming height = 1 for root)

        // balancedTree.inOrderTraversal();
    }

    public static BinarySearchTree solve(int[] arr)
    {
        BinarySearchTree tree = new BinarySearchTree();
        solveHelper(tree, arr, 0, arr.length);
        return tree;
    }

    private static void solveHelper(BinarySearchTree tree, int[] arr, int low, int high)
    {
        if (low >= high)
            return;

        int mid =  low + (high - low) / 2;
        tree.add(arr[mid]);
        solveHelper(tree, arr, low, mid);
        solveHelper(tree, arr, mid+1, high);
    }
}