0108.md

108. Convert Sorted Array to Binary Search Tree

Level:

Topic:

Similar Problem:

• 1382. Balance a Binary Search Tree

Question

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

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Intuition

Recursive:

• build the node based on the current range mid position
• the root value is alway the median value of the list

Code

Time: O(n)
Space: O(n)

Recursive

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


private TreeNode buildBST(int[] nums, int low, int high) {
    if (low > high)
        return null;

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