Convert Sorted Array to Balanced BST in DSA Python

Mental Model

We pick the middle element of the sorted array as the root to keep the tree balanced. Then we do the same for left and right halves to build left and right subtrees.

Analogy: Imagine dividing a sorted list of books evenly into two piles, picking the middle book as the main one, then repeating the process for each pile to build a balanced bookshelf.

Sorted array: [1, 2, 3, 4, 5, 6, 7]
Balanced BST:
      4
    /   \
   2     6
  / \   / \
 1   3 5   7

Dry Run Walkthrough

Input: sorted array: [1, 2, 3, 4, 5, 6, 7]

Goal: Build a balanced binary search tree from the sorted array

Step 1: Pick middle element 4 as root

Tree: 4
Array split: left=[1,2,3], right=[5,6,7]

Why: Middle element keeps tree balanced by dividing array evenly

Step 2: Build left subtree from [1,2,3], pick middle 2 as left child

Tree:
    4
   /
  2
Array split left: [1], right: [3]

Why: Recursively apply same logic to left half

Step 3: Build left child of 2 from [1], pick 1

Tree:
    4
   /
  2
 /
1

Why: Single element becomes leaf node

Step 4: Build right child of 2 from [3], pick 3

Tree:
    4
   /
  2
 / \
1   3

Why: Single element becomes leaf node

Step 5: Build right subtree from [5,6,7], pick middle 6 as right child

Tree:
    4
   / \
  2   6
 / \

Why: Recursively apply same logic to right half

Step 6: Build left child of 6 from [5], pick 5

Tree:
    4
   / \
  2   6
 / \  /
1   3 5

Why: Single element becomes leaf node

Step 7: Build right child of 6 from [7], pick 7

Tree:
    4
   / \
  2   6
 / \ / \
1  3 5  7

Why: Single element becomes leaf node

Result:

Balanced BST:
      4
    /   \
   2     6
  / \   / \
 1   3 5   7

Annotated Code

DSA Python

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

def sorted_array_to_bst(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])  # pick middle as root
    root.left = sorted_array_to_bst(nums[:mid])  # build left subtree
    root.right = sorted_array_to_bst(nums[mid+1:])  # build right subtree
    return root

def print_bst(root):
    if not root:
        return "null"
    left = print_bst(root.left)
    right = print_bst(root.right)
    return f"{root.val} -> ({left}, {right})"

# Driver code
nums = [1, 2, 3, 4, 5, 6, 7]
root = sorted_array_to_bst(nums)
print(print_bst(root))

mid = len(nums) // 2

Find middle index to keep tree balanced

root = TreeNode(nums[mid]) # pick middle as root

Create root node with middle element

root.left = sorted_array_to_bst(nums[:mid]) # build left subtree

Recursively build left subtree from left half

root.right = sorted_array_to_bst(nums[mid+1:]) # build right subtree

Recursively build right subtree from right half

Output

4 -> (2 -> (1 -> (null, null), 3 -> (null, null)), 6 -> (5 -> (null, null), 7 -> (null, null)))

Complexity Analysis

Time: O(n) because we visit each element once to create nodes

Space: O(log n) due to recursion stack depth for balanced tree

vs Alternative: Naive approach might build unbalanced tree causing O(n) recursion depth; this method keeps tree balanced for efficient operations

Edge Cases

empty array

returns None, no tree created

DSA Python

if not nums:
        return None

single element array

creates a single node tree

DSA Python

mid = len(nums) // 2

array with two elements

middle index 1 picks second element as root, first as left child

DSA Python

root.left = sorted_array_to_bst(nums[:mid])

When to Use This Pattern

When you see a sorted array and need a balanced binary search tree, use the middle element as root and recursively build subtrees from halves to keep balance.

Common Mistakes

Mistake: Picking first or last element as root instead of middle
Fix: Always pick middle element to keep tree balanced

Mistake: Not handling empty array base case causing infinite recursion
Fix: Add base case to return None when array is empty

Summary

Builds a balanced binary search tree from a sorted array by choosing middle elements as roots.

Use when you want a height-balanced BST from sorted data for efficient search.

The key is picking the middle element to keep left and right subtrees balanced.

Practice

1. What is the main goal when converting a sorted array to a balanced Binary Search Tree (BST)?

easy

A. To create a BST with minimal height

B. To create a linked list from the array

C. To reverse the array elements

D. To sort the array again

Solution

1. Step 1: Understand the problem goal

   The goal is to convert a sorted array into a BST that is balanced, meaning the tree height is minimized for efficient operations.

2. Step 2: Reason about balanced BST

   A balanced BST has roughly equal nodes on left and right subtrees, which reduces height and improves search time.

3. Final Answer:

   To create a BST with minimal height -> Option A

4. Quick Check:

   Balanced BST = minimal height [OK]

Hint: Pick option about minimal height balanced BST [OK]

Common Mistakes:

• Thinking the array is reversed
• Confusing BST with linked list
• Ignoring balance and height

2. Which of the following Python function signatures is correct for converting a sorted array nums to a balanced BST using recursion?

easy

A. def sortedArrayToBST(nums: list) -> int:

B. def sortedArrayToBST(nums: int) -> TreeNode:

C. def sortedArrayToBST(nums: list[int]) -> Optional[TreeNode]:

D. def sortedArrayToBST(nums: list[int]) -> list[int]:

Solution

1. Step 1: Check parameter type

   The input is a sorted array, so nums should be a list of integers: list[int].

2. Step 2: Check return type

   The function returns the root of a BST, which is a TreeNode or None, so Optional[TreeNode] is correct.

3. Final Answer:

   def sortedArrayToBST(nums: list[int]) -> Optional[TreeNode]: -> def sortedArrayToBST(nums: list[int]) -> Optional[TreeNode]:

4. Quick Check:

   Input list[int], output Optional[TreeNode] [OK]

Hint: Look for list input and TreeNode output signature [OK]

Common Mistakes:

• Using int instead of list[int] for input
• Returning int or list instead of TreeNode
• Missing Optional for possible None return

3. What is the output tree structure (inorder traversal) after running this code?

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

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

root = sortedArrayToBST([-10, -3, 0, 5, 9])

# Inorder traversal function
def inorder(node):
    return inorder(node.left) + [node.val] + inorder(node.right) if node else []

print(inorder(root))

medium

A. [0, -10, -3, 5, 9]

B. [-10, -3, 0, 5, 9]

C. [9, 5, 0, -3, -10]

D. [5, 9, 0, -3, -10]

Solution

1. Step 1: Understand inorder traversal

   Inorder traversal of a BST returns the sorted array in ascending order.

2. Step 2: Trace the code output

   The code builds a balanced BST from the sorted array, so inorder traversal returns the original sorted array: [-10, -3, 0, 5, 9].

3. Final Answer:

   [-10, -3, 0, 5, 9] -> Option B

4. Quick Check:

   Inorder traversal = sorted array [OK]

Hint: Inorder traversal of BST equals sorted array [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Expecting reversed or shuffled output
• Not understanding recursion splits

4. Identify the error in this code snippet for converting a sorted array to a balanced BST:

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

medium

A. TreeNode initialization missing value

B. Mid index calculation is incorrect

C. Base case condition is wrong

D. Left and right subtree slices are swapped

Solution

1. Step 1: Check subtree assignments

   The left subtree should be built from elements before mid: nums[:mid], and right subtree from elements after mid: nums[mid+1:].

2. Step 2: Identify swapped slices

   The code assigns left subtree from nums[mid+1:] and right subtree from nums[:mid], which is reversed.

3. Final Answer:

   Left and right subtree slices are swapped -> Option D

4. Quick Check:

   Left subtree = nums[:mid], right subtree = nums[mid+1:] [OK]

Hint: Remember left subtree < mid, right subtree > mid [OK]

Common Mistakes:

• Swapping left and right subtree slices
• Incorrect base case check
• Wrong mid index calculation

5. Given a sorted array with duplicate values [1, 2, 2, 3, 4, 4, 5], which approach correctly builds a balanced BST that includes all duplicates?

hard

A. Always pick leftmost element as root to handle duplicates

B. Remove duplicates first, then build BST

C. Use middle element as root, recursively build left and right subtrees including duplicates

D. Build BST by inserting elements one by one from left to right

Solution

1. Step 1: Understand duplicates in sorted array

   Duplicates appear consecutively; to keep all, do not remove them before building BST.

2. Step 2: Balanced BST construction with duplicates

   Picking the middle element as root and recursively building left and right subtrees preserves duplicates and balance.

3. Final Answer:

   Use middle element as root, recursively build left and right subtrees including duplicates -> Option C

4. Quick Check:

   Middle element root keeps duplicates balanced [OK]

Hint: Keep duplicates, use middle element recursively [OK]

Common Mistakes:

• Removing duplicates before building BST
• Picking always leftmost element as root
• Inserting elements one by one causing imbalance