3
\$\begingroup\$

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;

        }

    }
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Oh great!! Didn't think about using a helper function. Using this, I can change the start and end value according to left and right array. This will save the extra space.. Thanks a lot for suggestion.. \$\endgroup\$ – Mosbius8 Feb 16 '16 at 8:30
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.