LeetCode 108: Convert Sorted Array to Binary Search Tree Solution in Python Explained

Problem Statement

In LeetCode 108, you’re given a sorted integer array nums in ascending order. Your task is to convert it into a height-balanced BST and return its root. A height-balanced BST ensures the depth difference between left and right subtrees is at most 1 for every node. This differs from bottom-up traversal like LeetCode 107: Binary Tree Level Order Traversal II, focusing on tree construction from a sorted sequence.

Constraints

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in strictly increasing order

Example

Let’s see some cases:

Copy codeInput: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5] or similar
      0
     / \
   -3   9
   /   /
 -10  5
Explanation: Height-balanced BST, e.g., root 0, left [-10,-3], right [5,9].

Copy codeInput: nums = [1,3]
Output: [3,1] or [1,null,3]
      3    or    1
     /          \
    1            3
Explanation: Either is valid, balanced with depth difference ≤ 1.

Copy codeInput: nums = [1]
Output: [1]
Explanation: Single node, trivially balanced.

These examples show we’re building a balanced BST from a sorted array.

Understanding the Problem

How do you solve LeetCode 108: Convert Sorted Array to Binary Search Tree in Python? Take nums = [-10,-3,0,5,9]. We need a height-balanced BST, like [0,-3,9,-10,null,5]—root at the midpoint (0), left subtree [-10,-3], right subtree [5,9]. The sorted order ensures BST properties (left < root < right). This isn’t a postorder-based construction like LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal; it’s about balancing a sorted array. We’ll use: 1. Recursive Midpoint Division: O(n) time, O(h) space—our best solution. 2. Iterative with Queue: O(n) time, O(w) space—an alternative.

Let’s dive into the best solution.

Best Solution: Recursive Midpoint Division Approach

Explanation

Recursive Midpoint Division constructs a height-balanced BST by selecting the array’s midpoint as the root, recursively building left and right subtrees from the subarrays before and after the midpoint. This ensures balance (subtree depths differ by ≤ 1) and BST properties (left < root < right). It’s the best solution due to its O(n) time complexity, minimal space usage, and intuitive divide-and-conquer approach, perfectly suited for a sorted array.

For [-10,-3,0,5,9]:

• Midpoint: 0, Left: [-10,-3], Right: [5,9].
• Left mid: -3, Left: [-10], Right: [].
• Right mid: 9, Left: [5], Right: [].
• Result: [0,-3,9,-10,null,5].

Step-by-Step Example

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

Example 1: nums = [-10,-3,0,5,9]

Goal: Return [0,-3,9,-10,null,5] or similar balanced BST.

• Start: build(0, 5).
• Step 1: mid = 2, Root = nums[2] = 0.
• Left: build(0, 2).
• mid = 1, Root = -3.
• Left: build(0, 1) → -10.
• Right: build(2, 2) → None.
• Return -3->-10.
• Right: build(3, 5).
• mid = 4, Root = 9.
• Left: build(3, 4) → 5.
• Right: build(5, 5) → None.
• Return 9->5.
• Return 0->-3->9.
• Finish: [0,-3,9,-10,null,5].

Example 2: nums = [1,3]

Goal: Return [3,1] or [1,null,3].

• Start: build(0, 2).
• Step 1: mid = 1, Root = 3.
• Left: build(0, 1) → 1.
• Right: build(2, 2) → None.
• Finish: [3,1].

Example 3: nums = [1]

Goal: Return [1].

• Start: build(0, 1).
• Step 1: mid = 0, Root = 1.
• Left: None, Right: None.
• Finish: Return [1].

How the Code Works (Recursive Midpoint Division) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

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

def sortedArrayToBST(nums: list[int]) -> TreeNode:
    # Line 1: Define recursive builder function
    def build(start: int, end: int) -> TreeNode:
        # start = left index, end = right index (exclusive)
        # e.g., (0, 5) for [-10,-3,0,5,9]

        # Line 2: Base case - no nodes to process
        if start >= end:
            # If range is empty (e.g., 0 >= 0), return None
            return None

        # Line 3: Find midpoint index
        mid = (start + end) // 2
        # Midpoint splits array (e.g., (0+5)//2 = 2, nums[2]=0)
        # Ensures balance by choosing middle element

        # Line 4: Create root node with midpoint value
        root = TreeNode(nums[mid])
        # New node with mid value (e.g., 0)

        # Line 5: Recursively build left subtree
        root.left = build(start, mid)
        # Uses subarray before mid (e.g., 0 to 2 for [-10,-3])
        # Builds left subtree (e.g., -3->-10)

        # Line 6: Recursively build right subtree
        root.right = build(mid + 1, end)
        # Uses subarray after mid (e.g., 3 to 5 for [5,9])
        # Builds right subtree (e.g., 9->5)

        # Line 7: Return constructed subtree
        return root
        # Returns root of current subtree (e.g., 0->-3->9)

    # Line 8: Start construction with full array
    return build(0, len(nums))
    # Initiates with full range (e.g., 0, 5)
    # Returns root of balanced BST

This detailed breakdown clarifies how recursive midpoint division efficiently constructs a height-balanced BST.

Alternative: Iterative with Queue Approach

Explanation

Iterative with Queue builds the BST level-by-level using a queue to manage nodes and their index ranges, calculating midpoints to assign values and enqueue children. It’s a practical alternative, mimicking BFS-like construction while ensuring balance, though it uses more space.

For [-10,-3,0,5,9]:

• Queue: [(root, 0, 5)], mid=2, root=0.
• Left (0,2), Right (3,5).
• Result: [0,-3,9,-10,null,5].

Step-by-Step Example (Alternative)

For [-10,-3,0,5,9]:

• Start: queue = [(root, 0, 5)].
• Step 1: Pop (root, 0, 5), mid = 2, root = 0.
• Left: Enqueue (left, 0, 2).
• Right: Enqueue (right, 3, 5).
• Step 2: Pop (left, 0, 2), mid = 1, left = -3.
• Left: Enqueue (-10, 0, 1).
• Step 3: Pop (right, 3, 5), mid = 4, right = 9.
• Left: Enqueue (5, 3, 4).
• Step 4: Pop (-10, 0, 1), leaf.
• Step 5: Pop (5, 3, 4), leaf.
• Finish: [0,-3,9,-10,null,5].

How the Code Works (Iterative with Queue)

Copy codefrom collections import deque

def sortedArrayToBSTIterative(nums: list[int]) -> TreeNode:
    if not nums:
        return None
    root = TreeNode(0)  # Placeholder
    queue = deque([(root, 0, len(nums))])
    while queue:
        node, start, end = queue.popleft()
        if start >= end:
            continue
        mid = (start + end) // 2
        node.val = nums[mid]
        if start < mid:
            node.left = TreeNode(0)
            queue.append((node.left, start, mid))
        if mid + 1 < end:
            node.right = TreeNode(0)
            queue.append((node.right, mid + 1, end))
    return root

Complexity

• Recursive Midpoint Division:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack, h = height.
• Iterative with Queue:
• Time: O(n) – processes each node once.
• Space: O(w) – queue size, w = max width.

Efficiency Notes

Recursive Midpoint Division is the best solution with O(n) time and O(h) space, offering a concise, efficient approach—Iterative with Queue matches time complexity with O(w) space, providing a level-wise alternative that’s more explicit but uses extra memory.

Key Insights

• Midpoint: Ensures balance.
• Sorted Array: Guarantees BST properties.
• Recursion: Simplifies division.

Additional Example

For nums = [1,2,3,4]:

• Goal: [2,1,3,null,4] or similar.
• Recursive: Mid = 2, Left: [1], Right: [3,4].

Edge Cases

• Single Node: [1] → [1].
• Two Nodes: [1,2] → [1,null,2].
• Empty: [] → None.

Both solutions handle these well.

Final Thoughts

LeetCode 108: Convert Sorted Array to Binary Search Tree in Python is a foundational BST challenge. The Recursive Midpoint Division solution excels with its efficiency and clarity, while Iterative with Queue offers a level-wise alternative. Want more? Try LeetCode 94: Binary Tree Inorder Traversal for traversal basics or LeetCode 98: Validate Binary Search Tree for BST validation. Ready to practice? Solve LeetCode 108 on LeetCode with [-10,-3,0,5,9], aiming for [0,-3,9,-10,null,5]—test your skills now!