= Solution
Choose the middle element as the root:
``
build :: [a] -> Tree a
build [] = Empty
build xs = Tree (build ls) x (build rs)
where
(ls,x:rs) = splitAt (length xs `div` 2) xs
``
The input is a finite, strictly ascending <list>, as required for distinct elements of a <set>. The two child lengths differ by at most one. Applying the same argument recursively gives a <balanced binary tree> of logarithmic height. All values on each side retain their original order, proving the <binary search tree> property. With linked lists, the repeated splitting gives $O(n\log n)$ time; it does not repeatedly insert values into a skewed tree.
Back to article page
