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

#
# @lc app=leetcode id=108 lang=python3
#
# [108] Convert Sorted Array to Binary Search Tree
#
# Difficulty: Easy
# Frequency: 49.7%
# Tags: Array, Divide and Conquer, Tree, Binary Search Tree, Binary Tree
# URL: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
#
# --- Problem Description ---
#
# 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 <= 10^(4)
# 	  - -10^(4) <= nums[i] <= 10^(4)
# 	  - nums is sorted in a strictly increasing order.
#

#
# --- Community Solutions ---
#
# https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/solutions
#

# @lc code=start
# 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

# Divide & Conquer (Recursion) - O(n) time, O(log n) space (recursion depth)
#
# Intuition: the array is already sorted, so the middle element is the
# perfect root — everything left is smaller, everything right is larger.
# Recursively do the same for each half to build balanced left/right subtrees.
# Picking the middle each time guarantees the tree is height-balanced,
# because both halves are roughly equal size.
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        # FIX: check empty, not len==1. Recursion produces empty slices
        # e.g. nums[:0] → []. Without this, it crashes on empty input.
        if not nums:
            return None
        middle_idx = len(nums) // 2
        # FIX: need self. — it's a method call, not a standalone function
        left_tree = self.sortedArrayToBST(nums[:middle_idx])       # left half → left subtree
        right_tree = self.sortedArrayToBST(nums[middle_idx + 1:])  # right half → right subtree
        # FIX: need return! Without it, the node is created but thrown away,
        # and the function returns None — parent never receives its child.
        return TreeNode(nums[middle_idx], left_tree, right_tree)    # build root from middle


# @lc code=end