Inserting an already sorted sequence into a plain binary search tree one value at a time can produce a long chain. Searches then lose the advantage of a shallow tree. Instead, build the tree from the middle outward: choose a middle element as the root and repeat the choice for each half.
This conversion from a sorted array to a height-balanced BST creates every node once. The left and right portions differ in size by at most one at each split, so neither side grows into the chain produced by inserting values in sorted order.
Sorted Array to BST: Choose the Root
Suppose the input is [-10, -3, 0, 5, 9]. Its middle value, 0, becomes the root. Values to its left are smaller, and values to its right are larger. Apply the same rule to [-10, -3] and [5, 9] to create the root’s left and right subtrees.
For this example, use the lower middle element when a portion has an even number of values. The resulting tree is:
0
/ \
-10 5
\ \
-3 9
An in-order traversal visits the left subtree, the node, then the right subtree. Here it returns [-10, -3, 0, 5, 9], the original order. Different middle choices can produce a different valid tree; choosing the upper middle for an even-sized portion is also consistent if applied throughout.
To convert a sorted array to a binary search tree, the input must be in ascending order for this comparison rule. The implementation below assumes distinct values, so all keys in a left subtree are strictly smaller and all keys in a right subtree are strictly larger. Duplicate values need a policy before construction, discussed below.
Build With Inclusive Index Bounds
Rather than copy portions of the array at each step, pass the first and last indices of the current portion. Both bounds are inclusive. If left is greater than right, the portion is empty and its subtree is None. Otherwise, (left + right) // 2 identifies the lower middle index.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def sorted_array_to_bst(values):
def build(left, right):
if left > right:
return None
mid = (left + right) // 2
node = Node(values[mid])
node.left = build(left, mid - 1)
node.right = build(mid + 1, right)
return node
return build(0, len(values) - 1)
root = sorted_array_to_bst([-10, -3, 0, 5, 9])
print(root.value) # 0
print(root.left.value) # -10
print(root.left.right.value) # -3
To convert a sorted array to a binary search tree with these bounds, the left recursive call ends at mid - 1 and the right call starts at mid + 1. Neither call includes the root a second time. Together, the root and the two remaining ranges account for every input index exactly once.
For an empty list, the initial call is build(0, -1). The base case returns None immediately. For a single value, the middle is that value’s index, and both child calls have empty ranges. These two cases are worth testing because they reveal missing base cases and off-by-one errors.
Follow the Indices
With five values, the initial bounds are 0 and 4, so the midpoint is 2 and the root is 0. The left call receives 0 through 1; its midpoint is 0, giving node -10. Its left call receives 0 through -1 and returns None. Its right call receives 1 through 1, giving node -3.
The right call from the root receives 3 through 4, so it chooses index 3, value 5. Its remaining right range contains index 4, value 9. The completed conversion from sorted array to BST produces the pictured tree. Writing the bounds beside each call is an effective way to check an implementation before running it.
This approach differs from inserting a new value into an existing tree. Insertion follows comparisons until it finds one empty child position; it normally leaves the other nodes where they are. Here the complete sorted array is available in advance, and the algorithm chooses positions for all nodes to obtain a balanced initial shape. Rebuilding an existing tree from its sorted contents is a separate operation with its own cost.
Decide How to Handle Duplicates
The sample function assumes distinct input and does not validate that assumption. If duplicates are possible, decide what equality means before you convert a sorted array to a binary search tree. A simple option for set-like behavior is to remove duplicate keys before building the tree. If occurrences matter, store one node per distinct key with a count; that keeps the strict ordering rule while retaining frequency information.
You can instead define a tree in which equal keys are allowed on a particular side, but a naive midpoint split can put equal values on both sides of a node. Choosing a boundary to enforce one-sided equality may also create an unbalanced tree when many keys are equal. The same policy must be used by search, insertion, and deletion, so document it as part of the data structure rather than treating it as a minor implementation detail.
Time, Space, and Height
To convert a sorted array to a binary search tree, the algorithm creates one node per input value. Each call does constant work apart from its recursive calls, so total running time is O(n). The output itself occupies O(n) space. Because each split leaves subarrays whose sizes differ by at most one, the recursion stack uses O(log n) space for nonempty input.
The midpoint rule gives a height-balanced tree: at every node, the heights of the two child subtrees differ by at most one. Its height is O(log n), so a search follows O(log n) nodes in the worst case for the tree just built. Later ordinary insertions can change its shape; building a balanced tree once does not make subsequent updates self-balancing.
A sorted array to BST conversion is useful when ordered values are already available and you need a linked tree representation. If the data stays in an array and only lookup is required, binary search on the array also offers O(log n) lookup without allocating nodes. If frequent updates must preserve balance, consider a self-balancing tree with update operations designed for that purpose.
