Introduction to Convert Sorted Array to BST
The "Convert Sorted Array to Binary Search Tree" problem is a classic algorithmic challenge that frequently appears in coding interviews and competitive programming. Given an integer array sorted in ascending order, the task is to build a height-balanced binary search tree (BST) from those values. A height-balanced BST is one where the depth of the two subtrees of every node never differs by more than one.
This problem elegantly combines two fundamental computer science concepts: binary search and tree construction. Understanding how to solve it will sharpen your recursive thinking and deepen your grasp of tree data structures.
What Is a Binary Search Tree?
A binary search tree is a node-based binary tree structure that maintains a strict ordering property. For every node in the tree, all values in its left subtree are smaller than the node's value, and all values in its right subtree are larger. This ordering enables efficient search, insertion, and deletion operations, typically running in O(log n) time when the tree is balanced.
A height-balanced BST is especially desirable because it guarantees that operations remain efficient. If a BST becomes skewed—essentially degenerating into a linked list—those same operations degrade to O(n) time complexity. This is why converting a sorted array into a balanced BST, rather than simply inserting elements one by one, is so important.
Why This Problem Matters
- Interview relevance: It tests recursion, tree manipulation, and divide-and-conquer thinking in a single problem.
- Real-world applications: Balanced BSTs power database indexes, in-memory ordered maps, and range query systems.
- Foundation for advanced structures: Concepts here extend to AVL trees, red-black trees, and segment trees.
- Algorithmic intuition: It teaches how sorted data can be leveraged to build optimal structures.
Understanding the Core Insight
The key insight is remarkably simple: the middle element of a sorted array makes the best root node for a balanced BST. Why? Because choosing the middle element ensures that roughly half the elements go to the left subtree and half go to the right subtree. This naturally produces a height-balanced tree.
Once you pick the middle element as the root, the same logic applies recursively. The left half of the array forms the left subtree, and the right half forms the right subtree. This divide-and-conquer approach continues until the subarray is empty, at which point you return None as the leaf's child.
Defining the Tree Node
Before implementing the conversion, we need a class to represent tree nodes. In Python, this is typically done with a simple class containing a value and references to left and right children.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
This minimal definition is sufficient. Each node stores its integer value and pointers to its two children, which default to None for leaf nodes.
Step-by-Step Recursive Solution
Step 1: Identify the Base Case
Every recursive solution needs a base case to terminate. Here, when the subarray is empty—meaning the left index exceeds the right index—we return None. This represents the absence of a node, which happens at leaf boundaries.
Step 2: Find the Middle Element
Compute the middle index using mid = (left + right) // 2. This element becomes the root of the current subtree. Using integer division ensures we always get a valid index even when the subarray has an even number of elements.
Step 3: Create the Node and Recurse
Create a TreeNode with the middle value. Then recursively build the left subtree from the elements before the middle index, and the right subtree from the elements after the middle index.
Complete Implementation
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):
"""
Converts a sorted array into a height-balanced BST.
Args:
nums: List[int] - a list of integers sorted in ascending order
Returns:
TreeNode - the root of the constructed BST
"""
def build(left, right):
# Base case: empty subarray
if left > right:
return None
# Find the middle element
mid = (left + right) // 2
# Create the root node for this subtree
root = TreeNode(nums[mid])
# Recursively build left and right subtrees
root.left = build(left, mid - 1)
root.right = build(mid + 1, right)
return root
return build(0, len(nums) - 1)
Tracing Through an Example
Let us trace through the array [-10, -3, 0, 5, 9] to understand how the tree takes shape.
The initial call is build(0, 4). The middle index is (0 + 4) // 2 = 2, so nums[2] = 0 becomes the root. The left subtree is built from indices 0 to 1, and the right subtree from indices 3 to 4.
For the left subtree, build(0, 1) computes mid = 0, making nums[0] = -10 the left child of 0. Then build(0, -1) returns None for its left child, and build(1, 1) makes nums[1] = -3 its right child.
For the right subtree, build(3, 4) computes mid = 3, making nums[3] = 5 the right child of 0. Then build(3, 2) returns None, and build(4, 4) makes nums[4] = 9 the right child of 5.
The resulting tree looks like this:
0
/ \
-10 5
\ \
-3 9
Verifying the Solution
To confirm the tree is correct, we can perform an in-order traversal. For a valid BST built from a sorted array, an in-order traversal should reproduce the original sorted array.
def inorder_traversal(root):
"""Returns the in-order traversal of a BST as a list."""
result = []
def traverse(node):
if node is None:
return
traverse(node.left)
result.append(node.val)
traverse(node.right)
traverse(root)
return result
# Test the solution
nums = [-10, -3, 0, 5, 9]
root = sorted_array_to_bst(nums)
print("Original array:", nums)
print("In-order traversal:", inorder_traversal(root))
# Output: Original array: [-10, -3, 0, 5, 9]
# In-order traversal: [-10, -3, 0, 5, 9]
We can also verify that the tree is height-balanced by computing the depth of each subtree:
def is_balanced(root):
"""Checks if a binary tree is height-balanced."""
def check(node):
if node is None:
return 0
left_depth = check(node.left)
if left_depth == -1:
return -1
right_depth = check(node.right)
if right_depth == -1:
return -1
if abs(left_depth - right_depth) > 1:
return -1
return max(left_depth, right_depth) + 1
return check(root) != -1
print("Is balanced:", is_balanced(root))
# Output: Is balanced: True
Complexity Analysis
Time complexity: O(n), where n is the number of elements in the array. Every element is visited exactly once to create a node.
Space complexity: O(log n) for the recursion stack in the average case, since the tree is height-balanced and the recursion depth equals the tree height. In the worst case of a completely unbalanced tree, this could be O(n), but our algorithm guarantees balance. Additionally, O(n) space is used for the nodes themselves, which is unavoidable since we must store n nodes.
Iterative Alternative
While the recursive solution is clean and intuitive, an iterative approach can avoid potential stack overflow for extremely large arrays. The iterative version uses a stack to simulate recursion, tracking node ranges explicitly.
def sorted_array_to_bst_iterative(nums):
"""
Iteratively converts a sorted array into a height-balanced BST.
Useful when avoiding recursion depth limits.
"""
if not nums:
return None
root = TreeNode(0)
stack = [(root, 0, len(nums) - 1)]
while stack:
node, left, right = stack.pop()
mid = (left + right) // 2
node.val = nums[mid]
if mid + 1 <= right:
node.right = TreeNode(0)
stack.append((node.right, mid + 1, right))
if left <= mid - 1:
node.left = TreeNode(0)
stack.append((node.left, left, mid - 1))
return root
This iterative version produces the same balanced tree but processes nodes using an explicit stack data structure rather than the call stack.
Handling Edge Cases
A robust solution must handle several edge cases gracefully:
- Empty array: When
numsis empty,build(0, -1)immediately hits the base case and returnsNone. - Single element: The array
[5]produces a tree with just a root node and no children. - Two elements: The array
[1, 2]produces a root of 1 with a right child of 2, which is still balanced. - Duplicate values: The algorithm works with duplicates, though the resulting tree may not be a strict BST depending on how duplicates are handled in your specific use case.
# Edge case tests
print(inorder_traversal(sorted_array_to_bst([])))
# Output: []
print(inorder_traversal(sorted_array_to_bst([5])))
# Output: [5]
print(inorder_traversal(sorted_array_to_bst([1, 2])))
# Output: [1, 2]
print(inorder_traversal(sorted_array_to_bst([1, 1, 2, 3, 3])))
# Output: [1, 1, 2, 3, 3]
Best Practices
- Always validate input: Check that the input array is actually sorted before building the tree, or document that the caller must provide sorted data.
- Use helper functions: Wrapping the recursive logic in an inner function keeps the public interface clean and avoids exposing implementation details like index parameters.
- Prefer integer division: Using
//instead of/ensures the middle index is always an integer, avoiding type errors. - Consider overflow in other languages: While Python handles arbitrarily large integers, in languages like Java or C++, use
left + (right - left) // 2to avoid integer overflow when computing the midpoint. - Test with traversals: Always verify your BST by performing an in-order traversal and comparing the output to the original sorted array.
- Document assumptions: Clearly state whether duplicates are allowed and how they should be positioned in the tree.
Common Mistakes to Avoid
One frequent error is using mid = (left + right) // 2 with incorrect boundary updates. If you accidentally pass mid instead of mid - 1 or mid + 1 to the recursive calls, you risk infinite recursion because the middle element would be processed repeatedly.
Another mistake is forgetting the base case. Without the if left > right: return None check, the recursion never terminates. Some beginners write if left == right as the base case, which works but misses the empty subarray scenario and can cause index errors.
A subtler issue arises when developers try to slice the array instead of using indices. While slicing works, it creates new lists at each recursive step, increasing both time and space complexity to O(n log n). Using index boundaries keeps the solution at O(n) time.
# AVOID: Array slicing approach (less efficient)
def sorted_array_to_bst_sliced(nums):
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = sorted_array_to_bst_sliced(nums[:mid])
root.right = sorted_array_to_bst_sliced(nums[mid + 1:])
return root
This slicing version is easier to read but less efficient due to the overhead of creating sublists at every level of recursion.
Conclusion
Converting a sorted array to a height-balanced BST is a beautiful demonstration of how the structure of input data can be exploited to build an optimal output structure. By consistently choosing the middle element as the root and recursing on the remaining halves, we achieve an O(n) solution that produces a perfectly balanced tree. The recursive approach is the most intuitive and widely used, while the iterative alternative offers a practical option for environments with strict recursion limits. Mastering this problem not only prepares you for technical interviews but also builds foundational intuition for more advanced tree-based algorithms and data structures. Whether you are building database indexes, implementing ordered maps, or simply sharpening your algorithmic skills, the principles behind this solution will serve you well across countless programming challenges.