leetcode-108 Convert Sorted Array to Binary Search Tree

# Given an integer array nums sorted in ascending order, convert it to a
# height-balanced binary search tree.
# A height-balanced BST is a BST where the depth of the two subtrees of every
# node never differs by more than one.
#
# 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 a valid answer.
#
# Example 2:
# Input: nums = [1,3]
# Output: [3,1] or [1,null,3]
#
# Constraints:
# 1 <= nums.length <= 10^4
# -10^4 <= nums[i] <= 10^4
# nums is sorted in strictly ascending order.

# 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

class Solution:
    # Approach 1: Recursive with array slicing
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None

        # Choose middle element as root
        mid = len(nums) // 2
        root = TreeNode(nums[mid])

        # Recursively build left and right subtrees
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid + 1:])

        return root

    # Approach 2: With indices (no slicing - more efficient)
    def sortedArrayToBST2(self, nums: List[int]) -> Optional[TreeNode]:
        def helper(left, right):
            if left > right:
                return None

            # Choose middle as root
            mid = (left + right) // 2
            root = TreeNode(nums[mid])

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

            return root

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

    # Approach 3: Choosing left-middle or right-middle for deterministic result
    def sortedArrayToBST3(self, nums: List[int]) -> Optional[TreeNode]:
        def helper(left, right):
            if left > right:
                return None

            # Always choose left-middle for consistent result
            mid = (left + right) // 2  # Left-middle
            # Or: mid = (left + right + 1) // 2  # Right-middle

            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)

            return root

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

# Time Complexity: O(n) - visit each element once
# Space Complexity: O(log n) - recursion depth for balanced tree
#                   O(n) if counting array slicing copies
#
# Algorithm:
# 1. Choose middle element as root (ensures balance)
# 2. All elements to left are < root (left subtree)
# 3. All elements to right are > root (right subtree)
# 4. Recursively apply to both halves
#
# Why middle element?
# - Divides array into two equal (or nearly equal) halves
# - Ensures left and right subtrees have similar heights
# - This guarantees height-balanced BST
#
# Height of resulting tree: O(log n)
#
# Multiple valid answers:
# - When array has even length, can choose left-middle or right-middle
# - Both produce valid height-balanced BSTs
# - For deterministic output, consistently choose one
#
# Related Problems:
# - Convert Sorted List to BST (LC 109) - need to find middle of linked list
# - Balance a BST (LC 1382) - convert to sorted array first
#
# AirBnB: Tests recursion and understanding of BST properties