Problem Description

You are given an integer array nums that is sorted in ascending order. Your task is to convert this sorted array into a height-balanced binary search tree (BST).

A height-balanced binary search tree is a binary tree where the depth of the two subtrees of every node never differs by more than 1. This means the tree should be as balanced as possible - the left and right subtrees of any node should have heights that differ by at most 1.

Since the input array is already sorted, you need to construct a BST that:

1. Maintains the BST property (left subtree values < root < right subtree values)
2. Is height-balanced to ensure optimal performance for tree operations

The key insight is to choose the middle element of the array (or subarray) as the root node at each step. This ensures the tree remains balanced since roughly half the elements will go to the left subtree and half to the right subtree.

For example, if you have nums = [-10, -3, 0, 5, 9]:

• Choose the middle element 0 as root
• Elements to the left [-10, -3] form the left subtree
• Elements to the right [5, 9] form the right subtree
• Recursively apply this process to build the complete tree

The solution uses a divide-and-conquer approach with recursion, where at each step:

• Find the middle index: mid = (left + right) // 2
• Create a node with nums[mid] as the value
• Recursively build the left subtree from elements [left, mid-1]
• Recursively build the right subtree from elements [mid+1, right]
• Return the constructed node

Intuition

When we need to build a height-balanced BST from a sorted array, the main challenge is ensuring the tree remains balanced. If we simply insert elements one by one from the sorted array, we'd end up with a skewed tree (essentially a linked list), which defeats the purpose of using a BST.

The key observation is that in a balanced BST, the root node should have approximately the same number of nodes in its left and right subtrees. Since our array is already sorted, we know that:

• All elements to the left of any index are smaller
• All elements to the right of any index are larger

This naturally suggests choosing the middle element as the root. Why? Because this choice automatically divides the remaining elements into two roughly equal halves - perfect for creating balanced subtrees.

Think of it like organizing a tournament bracket. To make it fair and balanced, you'd want each side of the bracket to have roughly the same number of participants. Similarly, by always choosing the middle element as the "dividing point" (root), we ensure that both subtrees get approximately n/2 elements.

The recursive pattern emerges naturally:

1. Pick the middle element as root (this becomes the "parent" in our tree)
2. Everything to the left of middle becomes the left subtree (all smaller values)
3. Everything to the right of middle becomes the right subtree (all larger values)
4. Apply the same logic recursively to each half

This approach guarantees balance because at each level of recursion, we're dividing the problem size roughly in half. The height difference between any two subtrees can never exceed 1 because we're always splitting as evenly as possible.

The beauty of this solution is that it leverages the sorted property of the input - we don't need to sort or rearrange anything, just strategically pick our root nodes to maintain balance while preserving the BST property.

Solution Approach

The solution implements a divide-and-conquer approach using recursion. We create a helper function dfs(l, r) that constructs a balanced BST from the subarray nums[l...r].

Implementation Details:

The recursive function dfs(l, r) works as follows:

1. Base Case: If l > r, the subarray is empty, so we return None (null node).

2. Find the Middle Element: Calculate the middle index using mid = (l + r) >> 1. The bit shift operation >> 1 is equivalent to integer division by 2, giving us mid = (l + r) // 2.

3. Create Root Node: Create a new TreeNode with value nums[mid]. This middle element becomes the root of the current subtree.

4. Recursively Build Subtrees:

   • Left subtree: Call dfs(l, mid - 1) to construct the left subtree from elements in range [l, mid-1]
   • Right subtree: Call dfs(mid + 1, r) to construct the right subtree from elements in range [mid+1, r]

5. Connect and Return: The TreeNode constructor is called with three arguments:

   TreeNode(nums[mid], dfs(l, mid - 1), dfs(mid + 1, r))

   This creates the node with:

   • val = nums[mid] (the node's value)
   • left = dfs(l, mid - 1) (left subtree)
   • right = dfs(mid + 1, r) (right subtree)

Initial Call: The process starts with dfs(0, len(nums) - 1), which considers the entire array.

Time Complexity: O(n) where n is the number of elements in the array. Each element is visited exactly once to create its corresponding node.

Space Complexity: O(log n) for the recursion stack in a balanced tree (the height of the tree). The total space including the output tree is O(n).

Why This Works: By always selecting the middle element as the root, we ensure that the number of nodes in the left and right subtrees differs by at most 1. This maintains the height-balanced property throughout the tree construction. The sorted nature of the input array guarantees that the BST property (left < root < right) is automatically satisfied.

Example Walkthrough

Let's walk through the solution with a small example: nums = [-10, -3, 0, 5, 9]

Initial Call: dfs(0, 4) (processing indices 0 through 4)

Step 1: First recursive call dfs(0, 4)

• Calculate middle: mid = (0 + 4) // 2 = 2
• Create root node with nums[2] = 0
• Make recursive calls:
  • Left: dfs(0, 1) for elements [-10, -3]
  • Right: dfs(3, 4) for elements [5, 9]

Step 2: Process left subtree dfs(0, 1)

• Calculate middle: mid = (0 + 1) // 2 = 0
• Create node with nums[0] = -10
• Make recursive calls:
  • Left: dfs(0, -1) returns None (base case: empty range)
  • Right: dfs(1, 1) for element [-3]

Step 3: Process dfs(1, 1)

• Calculate middle: mid = (1 + 1) // 2 = 1
• Create node with nums[1] = -3
• Both dfs(1, 0) and dfs(2, 1) return None (empty ranges)
• Return node(-3) with no children

Step 4: Complete left subtree

• Node(-10) gets right child = node(-3)
• Left subtree of root is complete

Step 5: Process right subtree dfs(3, 4)

• Calculate middle: mid = (3 + 4) // 2 = 3
• Create node with nums[3] = 5
• Make recursive calls:
  • Left: dfs(3, 2) returns None (empty range)
  • Right: dfs(4, 4) for element [9]

Step 6: Process dfs(4, 4)

• Calculate middle: mid = (4 + 4) // 2 = 4
• Create node with nums[4] = 9
• Both recursive calls return None
• Return node(9) with no children

Step 7: Complete right subtree

• Node(5) gets right child = node(9)
• Right subtree of root is complete

Final Tree Structure:

       0
      / \
    -10   5
      \    \
      -3    9

The tree is height-balanced:

• Root's left subtree has height 2
• Root's right subtree has height 2
• All subtrees maintain the height difference ≤ 1 property

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm visits each element in the input array exactly once to create a corresponding tree node. The recursive function dfs is called once for each element in nums:

• At each recursive call, we create one TreeNode which takes O(1) time
• Finding the middle index using mid = (l + r) >> 1 is O(1)
• The total number of nodes created equals the length of the input array n
• Therefore, the overall time complexity is O(n)

Space Complexity: O(log n)

The space complexity consists of two components:

1. Recursion call stack: Since we're building a balanced BST by always choosing the middle element as root, the height of the tree is O(log n). The maximum depth of recursive calls equals the height of the tree, so the call stack uses O(log n) space.
2. Output tree structure: While the created BST contains n nodes (which would be O(n) space), this is typically not counted as part of the space complexity since it's the required output.

Therefore, considering only the auxiliary space used by the algorithm (the recursion stack), the space complexity is O(log n).

Common Pitfalls

1. Off-by-One Errors in Index Calculation

One of the most common mistakes is incorrectly handling the indices when making recursive calls, particularly mixing up inclusive vs. exclusive bounds.

Incorrect Implementation:

def build_bst(left, right):
    if left >= right:  # Wrong! This skips single-element arrays
        return None
  
    mid = (left + right) // 2
    root = TreeNode(nums[mid])
    root.left = build_bst(left, mid)  # Wrong! This includes mid again
    root.right = build_bst(mid, right)  # Wrong! This includes mid again
    return root

Why it's wrong: Using left >= right as the base case with inclusive bounds will terminate too early when left == right, missing single-element subarrays. Additionally, including mid in recursive calls creates duplicates.

Correct Implementation:

def build_bst(left, right):
    if left > right:  # Correct base case for inclusive bounds
        return None
  
    mid = (left + right) // 2
    root = TreeNode(nums[mid])
    root.left = build_bst(left, mid - 1)  # Exclude mid
    root.right = build_bst(mid + 1, right)  # Exclude mid
    return root

2. Integer Overflow in Middle Calculation

While less common in Python due to arbitrary precision integers, in languages with fixed-size integers, calculating mid = (left + right) // 2 can cause overflow when left + right exceeds the maximum integer value.

Problematic approach (in languages with fixed integers):

mid = (left + right) // 2  # Can overflow if left + right > MAX_INT

Safe alternatives:

# Method 1: Avoid overflow by reordering operations
mid = left + (right - left) // 2

# Method 2: Using bit shift (shown in original solution)
mid = (left + right) >> 1  # Still can overflow in some languages

# Method 3: Most robust for languages with overflow concerns
mid = left + ((right - left) >> 1)

3. Choosing Wrong Middle Element for Even-Length Arrays

When the array has an even number of elements, there are two possible "middle" elements. Consistently choosing one approach is important for predictable behavior.

Example with array [1, 2, 3, 4]:

# Lower middle approach (default integer division)
mid = (0 + 3) // 2 = 1  # Chooses element at index 1 (value 2)

# Upper middle approach
mid = (0 + 3 + 1) // 2 = 2  # Chooses element at index 2 (value 3)

Both approaches create valid balanced BSTs, but they produce different tree structures. The solution should consistently use one approach. The standard approach (using integer division) picks the lower middle, which tends to create slightly more balanced trees when dealing with sequences of even-length subarrays.

4. Modifying the Original Array

Some developers might try to slice the array in each recursive call instead of passing indices:

Inefficient approach:

def sortedArrayToBST(self, nums):
    if not nums:
        return None
  
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = self.sortedArrayToBST(nums[:mid])  # Creates new array
    root.right = self.sortedArrayToBST(nums[mid+1:])  # Creates new array
    return root

Problems with this approach:

• Time complexity increases to O(n log n) due to array slicing
• Space complexity increases to O(n log n) for all the array copies
• Less efficient than index-based approach

Better approach: Use indices to track array segments without creating copies, as shown in the original solution.