108.convert-sorted-array-to-binary-search-tree.md

108. Convert Sorted Array to Binary Search Tree

Subarray

fun sortedArrayToBST(nums: IntArray): TreeNode? {
    val n = nums.size
    if (n == 0) return null
    if (n == 1) return TreeNode(nums[0])
    val middle = n / 2
    val root = TreeNode(nums[middle])
    root.left = sortedArrayToBST(nums.sliceArray(0..middle - 1))
    root.right = sortedArrayToBST(nums.sliceArray(middle + 1 until n))

    return root
}

In-Place

fun sortedArrayToBST(nums: IntArray): TreeNode? {
    return buildBST(nums, 0, nums.size - 1)
}

private fun buildBST(A: IntArray, start: Int, end: Int): TreeNode? {
    if (A.isEmpty() || start > end) return null
    // Remember to add `start`
    val middle = start + (end - start) / 2

    // Or we can use another way to calculate middle
    // val middle = (end + start) / 2
    
    val root = TreeNode(A[middle])
    root.left = buildBST(A, start, middle - 1)
    root.right = buildBST(A, middle + 1, end)
    return root
}

• Time Complexity: O(n), iterate all elements.
• Space Complexity: O(lg n), stack depth = tree height.