In this article, you will learn how to convert a sorted array to a balanced binary search tree. A balanced binary tree is a tree in which the left subtree’s height and the height of the right subtree of every node do not differ by a length greater than 1. On the other hand, in a binary search tree, the value of the root at every node is less than every node’s value in its right subtree and is greater than every node’s value in its left subtree.

How to Implement a Balanced Binary Tree in a Sorted Array?

Consider the following balanced binary search tree.

If we convert the above tree into a sorted array, we will get:

arr = [1, 3, 5, 6, 9, 12]

If we look at the obtained array, we can see that the root value of the tree lies in the middle of the array, i.e., 5. Its right node’s value lies in the middle of the right half (from index 3 to index 5), i.e.,

right_half = [6, 9, 12]
mid = 9

We can obtain the left node’s value by taking mid of the left half (from index 0 to index 1), i.e.,

left_half = [1, 3]
mid = 1

Similarly, if we divide right_half and left_half into two parts, we can obtain its left and right children by finding their middle values.

Therefore, following this pattern, we can find all nodes of the balanced binary search tree. Moreover, programmatically, we can convert a sorted array to a balanced BST using a recursive algorithm. The steps are given below:

Find the mid location of the array, i.e., mid = low + (high-low)/2 (integer division). Variables low and high represent the indices of the two ends of the current part. Initially, when the complete array gets considered, low is 0, and high is equal to the length of array – 1. Create a tree node with the value at the mid position. It represents the root of the subtree.

Recursively, do the following for the left and right parts:

• Find the middle of the left half and assign it as the left child of the root.
• Find the middle of the right half and assign it as the right child of the root.

Implementation

The implementation of the conversion of a sorted array to a balanced BST is given below.

#a tree node containing data and references
for left and right children
class TreeNode:
    def __init__(self, val, left = None, right = None):
    self.val = val
self.left = left
self.right = right

def convertToBST(array, low, high):
    if low <= high:
    mid = low + (high - low) //2 #get the mid of the array

root = TreeNode(array[mid])# create a node with the middle value and make it root of the subtree / tree

# recursively create the left subtree# Find the middle of the left half and assign it as the root 's left child.left = convertToBST(array, low, mid-1)

#
recursively create the right subtree# get the middle of the right half and assign it as the root
root 's right child.right = convertToBST(array, mid+1, high)
return root

# preorder traversal of the tree
def preOrderTraversal(root):
    if root == None:
    return None
print(root.val)
preOrderTraversal(root.left)
preOrderTraversal(root.right)


array = [1, 3, 5, 6, 9, 12]
root = convertToBST(array, 0, len(array) - 1)
preOrderTraversal(root)

Output

5
1
3
9
6
12