## Constructing a balanced Binary Search Tree from a sorted List in O(N) time

This post discusses a O(n) algorithm that construct a balanced binary search tree (BST) from a sorted list. For instance, consider that we are given a sorted list: `[1,2,3,4,5,6,7]`. We have to construct a balanced BST as follows.

```        4
|
2        6
|        |
1   3   5     7
```

To do so, we use the following definition of `Tree`, described in Scala By Example book.

```abstract class IntSet
case object Empty extends IntSet
case class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet
```

One straight-forward approach would be to repeatedly perform binary search on the given list to find the median of the list, and then, to construct a balanced BST recursively. Complexity of such approach is O(nlogn), where n is the number of elements in the given list.

A better algorithm constructs balanced BST while iterating the list only once. It begins with the leaf nodes and construct the tree in a bottom-up manner. As such, it avoids repeated binary searches and achieves better runtime complexity (i.e., O(n), where n is the total number of elements in the given list). Following Scala code outlines this algorithm, which effectively converts a list `ls` to an `IntSet`, a balanced BST:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 def toTree(ls: List[Int]): IntSet = { def toTreeAux(ls: List[Int], n: Int): (List[Int], IntSet) = { if (n <= 0) (ls, Empty) else { val (lls, lt) = toTreeAux(ls, n / 2) // construct left sub-tree val x :: xs = lls // extract root node val (xr, rt) = toTreeAux(xs, n - n / 2 - 1) // construct right sub-tree (xr, IntSet(x, lt, rt)) // construct tree } } val (ls_1, tree) = toTreeAux(ls, List.length(ls)) tree }
view raw toTree.scala hosted with ❤ by GitHub

Any comment or query regarding this post is highly appreciated. Thanks.