108. Convert Sorted Array to Binary Search Tree - Explanation

Problem Link

1. Depth First Search

Intuition

To create a height-balanced BST from a sorted array, we need to ensure that for every node, the left and right subtrees have roughly equal heights. Since the array is sorted, the middle element should become the root. All elements before the middle go to the left subtree, and all elements after go to the right subtree. Applying this recursively builds a balanced tree.

Algorithm

1. Base case: If the array is empty, return null.
2. Find the middle index of the current array segment.
3. Create a new tree node with the middle element as its value.
4. Recursively build the left subtree using the left half of the array (elements before the middle).
5. Recursively build the right subtree using the right half of the array (elements after the middle).
6. Return the root node.

# 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:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None

        mid = len(nums) // 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid + 1:])
        return root

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(n)$

---

2. Depth First Search (Optimal)

Intuition

The previous approach creates new array copies for each recursive call, which is inefficient. Instead, we can pass indices (left and right boundaries) to indicate the current segment of the array. This avoids array slicing and reduces both time and space overhead while maintaining the same logic of choosing the middle element as root.

Algorithm

1. Define a helper function that takes left and right boundary indices.
2. Base case: If left > right, return null (empty segment).
3. Calculate the middle index as (left + right) / 2.
4. Create a tree node with the value at the middle index.
5. Recursively build the left subtree with boundaries (left, mid - 1).
6. Recursively build the right subtree with boundaries (mid + 1, right).
7. Call the helper with initial boundaries (0, n - 1) and return the result.

# 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:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(l, r):
            if l > r:
                return None
            m = (l + r) // 2
            root = TreeNode(nums[m])
            root.left = helper(l, m - 1)
            root.right = helper(m + 1, r)
            return root

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

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity:
  • $O(\log n)$ space for recursion stack.
  • $O(n)$ space for the output.

---

3. Iterative DFS

Intuition

The recursive approach can be converted to an iterative one using an explicit stack. We store pending work items on the stack, where each item contains a node to be filled and the array bounds it should use. This simulates the recursive call stack and processes each subtree systematically without recursion.

Algorithm

1. If the array is empty, return null.
2. Create a root node with a placeholder value.
3. Push the root node along with its bounds (0, n-1) onto a stack.
4. While the stack is not empty:
   • Pop an item containing the node and its bounds (l, r).
   • Calculate the middle index and set the node's value to nums[mid].
   • If there are elements to the left (l <= mid - 1), create a left child and push it with bounds (l, mid - 1).
   • If there are elements to the right (mid + 1 <= r), create a right child and push it with bounds (mid + 1, r).
5. Return the root.

# 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:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None

        root = TreeNode(0)
        stack = [(root, 0, len(nums) - 1)]

        while stack:
            node, l, r = stack.pop()
            m = (l + r) // 2
            node.val = nums[m]
            if l <= m - 1:
                node.left = TreeNode(0)
                stack.append((node.left, l, m - 1))
            if m + 1 <= r:
                node.right = TreeNode(0)
                stack.append((node.right, m + 1, r))

        return root

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity:
  • $O(\log n)$ space for the stack.
  • $O(n)$ space for the output.

---

Common Pitfalls

Off-by-One Errors in Subarray Bounds

When recursively building subtrees, a common mistake is including the middle element in one of the subarrays, leading to infinite recursion or duplicate nodes.

# Wrong - includes mid in left subtree
root.left = helper(l, m)  # should be m - 1

# Correct
root.left = helper(l, m - 1)
root.right = helper(m + 1, r)

Choosing Wrong Middle Element in Even-Length Arrays

For arrays with even length, the middle can be either (l + r) // 2 or (l + r + 1) // 2. While both produce valid height-balanced BSTs, inconsistency can cause confusion. The problem accepts either choice, but stick with one consistently.