Build Balanced Binary Search Tree from Array

Introduction

This post describes the algorithm to build binary search tree from array of sorted elements. However, this technique can be used to build balanced binary search tree from array. A balanced binary tree is a binary tree which has minimum height.

To know more about various aspects of a binary search tree, please visit my previous posts.

What does balanced means?

In this post as we are trying to build a BST, we will assume the input to be a sorted array. In case, we are just building a binary tree, we can take any array as an input. Let me explain the process with the help of a small example.

We must realize that a perfectly balanced binary tree must have 2^N – 1 elements where N is the height of the tree. If the number of elements are not equal to 2^N – 1 then we won’t be able to create a perfect binary tree. However, it is reasonably balanced.

Example

Here are examples of a perfectly balanced binary tree and a nearly balanced binary tree. In the perfectly balanced tree the number of nodes is equal to 2^N-1. But, it wont be possible to comment on the number of nodes in a nearly balanced tree.

Build Balanced Binary Search Tree from Array

Approach to Build Balance Binary Search Tree from Array

Let us say that we have an array 1, 2, 3, 4, 5, 6, 7, 8, 9. Given this array, let us find what would make a tree out of these elements, such that it is a balanced tree?

The definition of binary tree, translates to having equal number of elements to the left and to the right, this will ensure that the tree is balanced. Now, if we can ensure this property to be true at each node, we will end up with a perfectly binary tree.

How can we ensure this to be true at each node?

The answer is divide and conquer. Let us divide the array in two halves, take the middle element and make it the root. Recursively, we can take the left half and divide it in two and make it the root of the left child. Doing the same with the right half will yield the root of the right child and then we can attach both the roots to the parent.

  • For the input array 1, 2, 3, 4, 5, 6, 7, 8, 9. The middle element is 5, hence 5 is the root of the tree.
  • Now the left array is 1, 2, 3, 4 and the right array is 6, 7, 8, 9
  • Operating on left sub array
    • Middle element can be chosen as 2 or 3. Let us choose 2 and make it the root of the left sub tree.
    • It divides the array into two halves, 1 and 3, 4
    • No need to divide the single element in the left. But we have to divide 3, 4 into two
      • Let 3 be the middle element, so its the root of the right sub tree. Now the only element left is 4, attach is to the root (3)
    • Attach 1 and 3 to the 2
  • In the same way operate on the right array 6, 7, 8, 9, let say the root of this sub array is 7
  • Hence, attach 2 and 7 to the root of the tree (which is 5).

Source Code

The above code requires the BSTNode data structure, which is defined below:

Here is how you would like to invoke the createTree method:

Analysis

As this is a recursive application, the run time can be written as a recurrence relation T(N) = 2T(N/2) + O(1). This recurrence relation holds when at each level the problem is divided into two sub problems of equal size. Also, by the definition of BST and logs, the height of the tree will be logN where N is the number of elements in the array.

Hence, the number of levels of recursion will be logN. Also, the recurrence equation is of the form which can be solved using Master’s method . The solution to this recurrence is O(NlogN)

The space required would be equal to the depth of the recursion stack, which is O(logN) as the height of the tree is logN