Introduction

In this blog post, we will explore how to solve the LeetCode problem "108" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. Example 1: 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: Example 2: Input: nums = [1,3] Output: [3,1] Explanation: [1,null,3] and [3,1] are both height-balanced BSTs. Constraints: 1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums is sorted in a strictly increasing order.

Explanation

Here's the breakdown of the solution:

• Divide and Conquer: The core idea is to recursively divide the sorted array into subarrays. The middle element of each subarray becomes the root of the (sub)tree.
• Balanced Tree Construction: Since the input array is sorted and we're always choosing the middle element as the root, the resulting tree will be height-balanced.

• Recursive Calls: Recursively apply the same logic to the left and right subarrays to build the left and right subtrees.

• Runtime & Storage Complexity: O(n), where n is the number of elements in nums. Space complexity is O(log n) due to the call stack during recursion, which is the height of the balanced BST.

Code

    class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sortedArrayToBST(nums):
    """
    Converts a sorted array to a height-balanced BST.

    Args:
        nums: A sorted array of integers.

    Returns:
        The root of the height-balanced BST.
    """

    def helper(left, right):
        if left > right:
            return None

        mid = (left + right) // 2
        root = TreeNode(nums[mid])

        root.left = helper(left, mid - 1)
        root.right = helper(mid + 1, right)

        return root

    return helper(0, len(nums) - 1)