Convert Sorted Array to Binary Search Tree

Problem Statement

LeetCode-108: Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

In the below mentioned example, the input array [-10,-3,0,5,9] can be represented as either [0,-3,9,-10,null,5] or [0,-10,5,null,-3,null,9].

Approach

The problem can be solved using recursion.

1. Use the middle element of the array as the root of the tree.
2. Recursively build the left subtree from the left half of the array.
3. Recursively build the right subtree from the left half of the array.
4. Return the root node.

The base case for the recursion is when the left index is greater than the right index.

Implementation

Here is a java implementation of the above approach:

public TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length -1);   
}

private TreeNode build(int[] nums, int start, int end){
    if(start <= end){
        int mid = start + (end - start)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, start, mid-1);
        root.right = build(nums, mid+1, end);
        return root;
    }
    return null;
}

Complexity Analysis

The time complexity for the above approach is $O(n)$ where $n$ is the number of elements in the array. The space complexity is $O(\log n)$ due to the recursion stack associated with a height balanced tree.