Skip to main content

Convert Sorted Array to Binary Search Tree

Problem Description​

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

Examples​

Example 1​

  • Input: nums = [-10,-3,0,5,9]
  • Output: [0,-3,9,-10,null,5]

Example 2​

  • Input: nums = [1,3]
  • Output: [3,1]

Constraints​

  • 1≤nums.length≤1041 \leq \text{nums.length} \leq 10^4
  • −104≤nums[i]≤104-10^4 \leq \text{nums}[i] \leq 10^4
  • nums is sorted in a strictly increasing order

Solution Code​

Python​

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        total_nums = len(nums)
        if not total_nums:
            return None

        mid_node = total_nums // 2
        return TreeNode(
            nums[mid_node], 
            self.sortedArrayToBST(nums[:mid_node]), self.sortedArrayToBST(nums[mid_node + 1 :])
        )

Java​

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        int n=nums.length;
        if (n ==0) return null;
        if (n ==1) {
            TreeNode head = new TreeNode(nums[0]);
            return head;
        }

        TreeNode head = buildBST(nums,0,n-1);
        return head;
    }
    private TreeNode buildBST (int [] nums, int low, int high){
        if(low>high) return null;

        int mid =low+(high-low)/2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left =buildBST(nums,low,mid-1);
        node.right =buildBST(nums,mid+1,high);
        return node;
    }
}

C++​

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return constructBSTRecursive(nums, 0, nums.size() - 1);
    }

    TreeNode* constructBSTRecursive(vector<int>& nums, int left, int right) {
        if(left > right)
            return NULL;
        int mid = left + (right - left) / 2;
        TreeNode* node = new TreeNode(nums[mid]);
        node->left = constructBSTRecursive(nums, left, mid - 1);
        node->right = constructBSTRecursive(nums, mid + 1, right);
        return node;
    }
};

Javascript​

var sortedArrayToBST = function(nums) {
    if(!nums.length) return null;
    let mid = Math.floor(nums.length / 2);
    let root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums.slice(0, mid));
    root.right = sortedArrayToBST(nums.slice(mid + 1));
    return root;
};