Make binary search tree from sorted array

Question

Here is my code for converting a sorted array to a binary search tree. Please review and let me know the improvements or some better way of solving this.

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        // If there is only one element, make it root node and return.
        if (nums.length == 1) {
            TreeNode root = new TreeNode(nums[0]);
            return root;
        }

        // else, find the mid element and the left of it as left and right to
        // right recursively
        else {
            int length = nums.length;
            TreeNode root = new TreeNode(nums[length / 2]);
            int[] numsLeft = Arrays.copyOfRange(nums, 0, nums.length / 2);
            int[] numsRight = Arrays.copyOfRange(nums, (nums.length / 2) + 1, nums.length);
            root.left = sortedArrayToBST(numsLeft);
            root.right = sortedArrayToBST(numsRight);
            return root;

        }

    }

Answer 1

Simplify

The special handling for nums.length == 1 is unnecessary. This works just as well:

public TreeNode sortedArrayToBST(int[] nums) {
    if (nums == null || nums.length == 0) {
        return null;
    }
    int length = nums.length;
    TreeNode root = new TreeNode(nums[length / 2]);
    int[] numsLeft = Arrays.copyOfRange(nums, 0, nums.length / 2);
    int[] numsRight = Arrays.copyOfRange(nums, (nums.length / 2) + 1, nums.length);
    root.left = sortedArrayToBST(numsLeft);
    root.right = sortedArrayToBST(numsRight);
    return root;
}

Improve

While your solution works, some aspects can be improved:

• Array copy is not cheap, it would be better to avoid
• The null check is only necessary on the first call, in recursive calls it will always be false

The way to solve both of these issues is to introduce a helper method taking the start and end points of a range in the source array. Something like this, the most juicy part omitted to avoid spoiling your exercise:

public TreeNode sortedArrayToBST(int[] nums) {
    if (nums == null) {
        return null;
    }

    return sortedArrayToBST(nums, 0, nums.length);
}

private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
    if (start == end) {
        return null;
    }

    // ...
}

Note that there is no more check on nums.length == 0, the start == end in the helper takes care of that. The function can be completed by adding a few lines with recursive calls, with adjusted range parameters.

Answer 2

You are creating new array for each of the recursive calls which means you are doing a lot of unnecessary memory allocation and it's time consuming at the same time. The space complexity can be reduced by making use of the indices for the same array. Rather than calling the length function for the array, you can keep track of start and end of the array and find the mid for the subarray. Just like you do for binary search implementation. Here is the code:-

public static TreeNode sortedArrayToBST(int[] nums) {
    if(nums == null){
        return null;
    }
    return sortedArrayToBST(nums, 0, nums.length - 1 );
}

private static TreeNode sortedArrayToBST(int[] nums, int s, int e) {

    if(s > e)
        return null;

    int mid = (s + e)/2;

    TreeNode root = new TreeNode(nums[mid]);

    root.left = sortedArrayToBST(nums, s, mid - 1 );
    root.right = sortedArrayToBST(nums, mid + 1 , e);

    return root;
}

This would be more space and time efficient.