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:

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 | |

} |

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