Convert Sorted Array to Binary Search Tree

07/11/2016 Tree Depth First Search

Question

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.


Solution

Result: Accepted Time: 4 ms

Here should be some explanations.

struct TreeNode * buildtree(int *nums,int low,int up)
{
    if(low >= up)
        return NULL;
    struct TreeNode * tmp = malloc(sizeof(struct TreeNode));
    int mid = low + ((up - low) >> 1);
    tmp->val = nums[mid];
    tmp->left = buildtree(nums,low,mid);
    tmp->right = buildtree(nums,mid+1,up);
    return tmp;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    return buildtree(nums,0,numsSize);
}

Complexity Analytics

  • Time Complexity:
  • Space Complexity: