# Building a Tree from an Ordered List

A nice recursive algorithm for building a nearly-optimal binary search
tree from an **ordered list**.:

```
data Tree a = Node a (Tree a) (Tree a)
| End
```

The algorithm `divide`

s the input list into sublists of increasing length:
1,2,4,8… The first element of each sublist is the “keystone” of a subtree
assembled with `mkTree`

. :

```
fromSorted :: [a] -> Tree a
fromSorted = foldl mkTree End . divide 1
where mkTree l (n:ns) = Node n l (fromSorted ns)
divide _ [] = []
divide c xs = take c xs : divide (c*2) (drop c xs)
```

Variations that used `splitAt`

instead of the separate `take`

and `drop`

were
no more efficient (perhaps because of
sharing?) nor was using the
strict `foldl'`

.

Anyone have a clever alternative to the divide function defined here? Or a different approach to the problem? Would love to hear it.