algoadvance

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

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example:

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:

Clarifying Questions

  1. Are there any constraints on the size of the input array?
    • Typically, array size constraints are reasonable for array to BST conversion problems, so we can assume this to be manageable within typical memory and execution limits.
  2. Is the input array guaranteed to be sorted in strictly increasing order?
    • Yes, as per the problem statement, the input array is already sorted in non-decreasing order.
  3. What should be the output format?
    • The output should be the root of the binary search tree.

Strategy

To create a height-balanced binary search tree from a sorted array, we can recursively select the middle element of the current subarray as the root. This ensures that the tree remains balanced, as the left and right subarrays will have roughly the same size.

Here is the strategy:

  1. Base Case: If the subarray is empty, return None.
  2. Recursive Case:
    • Find the middle index of the current subarray.
    • Create a tree node with the middle element as the root.
    • Recursively repeat the process for the left subarray to create the left child.
    • Recursively repeat the process for the right subarray to create the right child.

Code

from typing import List, Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sortedArrayToBST(nums: List[int]) -> Optional[TreeNode]:
    if not nums:
        return None
    
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid+1:])
    
    return root

Time Complexity

The time complexity of this solution is ( O(n) ), where ( n ) is the number of elements in the input array. This is because each element is processed exactly once to create the BST nodes.

The space complexity is ( O(\log n) ) for the recursive call stack in an optimally balanced BST, but in the worst case of highly unbalanced BST (though this is balanced by definition), we might consider ( O(n) ) due to the depth of the recursion tree.

This implementation guarantees a height-balanced binary search tree formed from the sorted input array.

Try our interview co-pilot at AlgoAdvance.com