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

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

## UVa 136. Ugly Numbers

This blog-post is about UVa 136: Ugly Number, a trivial, but interesting UVa problem. The crux involves computing 1500th Ugly number, where a Ugly number is defined as a number whose prime factors are only 2, 3 or 5. Following illustrates a sequence of Ugly numbers:

`1,2,3,4,5,6,8,9,10,12,15...`

Using F#, we can derive 1500th Ugly Number in F#’s REPL as follows.

In this context, the primary function the determines whether a number is a Ugly number or not–`isUglyNumber`–is outlined as follows. As we can see, it is a naive algorithm that can be further optimized using memoization (as listed here).

After computing the 1500th Ugly number in this manner, we submit the Java source code listed below. For complete source code. please visit this gist. Alternatively, this script is also available at tryfsharp.org for further introspection.

## UVa 371. Ackermann Function

The underlying concepts of UVa 371: Ackermann Functions have been discussed in great details in our post of Collatz problem. In this post, we simply outlines an ad-hoc algorithm as a solution to this problem as follows. SPOJ 42. Adding Reversed Numbers (ADDREV) with F#.