Make binary search tree from sorted array

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;

        }

    }

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.

StackExchange Code Review Q#120117, answer score: 4