Convert Sorted Array to Binary Search Tree

Difficulty: Easy | Acceptance: 75.50% | Paid: No Topics: Array, Divide and Conquer, Tree, Binary Search Tree, Binary Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Examples

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,3] and [3,1] are both a height-balanced BSTs.

Constraints

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums is sorted in strictly ascending order.

Recursive Divide and Conquer

Intuition To construct a height-balanced BST, the middle element of the sorted array must be the root. This ensures that the number of nodes in the left and right subtrees differ by at most one. We recursively apply this logic to the left and right subarrays.

Steps

• Find the middle index mid of the current subarray.
• Create a TreeNode with the value at nums[mid].
• Recursively build the left subtree using the subarray to the left of mid.
• Recursively build the right subtree using the subarray to the right of mid.
• Return the constructed 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]:
        def helper(left, right):
            if left > right:
                return None
            
            mid = (left + right) // 2
            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root
        
        return helper(0, len(nums) - 1)

Complexity

• Time: O(n) — We visit each node exactly once.
• Space: O(log n) — The recursion stack depth is proportional to the height of the tree, which is log n for a balanced tree.
• Notes: This is the most intuitive and standard approach for this problem.

Iterative Depth-First Search

Intuition We can simulate the recursive process using an explicit stack. This avoids the overhead of recursive function calls and potential stack overflow issues in languages with limited stack size, though the space complexity remains similar.

Steps

• Initialize a stack to store tuples of (left_index, right_index, parent_node, is_left_child).
• Push the initial range (0, length - 1, null, false) onto the stack.
• While the stack is not empty:
  • Pop a tuple.
  • Calculate the middle index mid.
  • Create a new node with nums[mid].
  • If the parent is null, this node is the root. Otherwise, attach it to the parent’s left or right child.
  • Push the right and left sub-ranges onto the stack to process them later.

# 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
        
        root = None
        # Stack stores: (left, right, parent_node, is_left_child)
        stack = [(0, len(nums) - 1, None, False)]
        
        while stack:
            l, r, parent, is_left = stack.pop()
            mid = (l + r) // 2
            node = TreeNode(nums[mid])
            
            if parent is None:
                root = node
            elif is_left:
                parent.left = node
            else:
                parent.right = node
            
            # Push right child range first so left is processed first (LIFO)
            if mid + 1 <= r:
                stack.append((mid + 1, r, node, False))
            if l <= mid - 1:
                stack.append((l, mid - 1, node, True))
                
        return root

Complexity

• Time: O(n) — We process each element exactly once.
• Space: O(n) — In the worst case, the stack can grow to the size of the array (e.g., for a skewed tree, though the input is sorted, the logic ensures balance, the stack holds pending ranges).
• Notes: Useful when recursion depth is a concern, though the recursive solution is generally preferred for readability.