```{- |
Description: Binary search trees
Maintainer: dev@chungyc.org

Some solutions to "Problems.P57" of Ninety-Nine Haskell "Problems".
-}

import           Problems.BinaryTrees

-- | Construct a binary search tree from a list of ordered elements.
construct :: Ord a => [a] -> Tree a
construct :: forall a. Ord a => [a] -> Tree a
construct [a]
l = [a] -> Tree a -> Tree a
forall {a}. Ord a => [a] -> Tree a -> Tree a
build [a]
l Tree a
forall a. Tree a
Empty
where build :: [a] -> Tree a -> Tree a
build [] Tree a
tree     = Tree a
tree
build (a
x:[a]
xs) Tree a
tree = [a] -> Tree a -> Tree a
build [a]
xs (a
x a -> Tree a -> Tree a
forall a. Ord a => a -> Tree a -> Tree a
tree)

-- | Return a binary search tree with an element added to another binary search tree.
addedTo :: Ord a => a -> Tree a -> Tree a
addedTo :: forall a. Ord a => a -> Tree a -> Tree a
x Tree a
Empty                 = a -> Tree a -> Tree a -> Tree a
forall a. a -> Tree a -> Tree a -> Tree a
Branch a
x Tree a
forall a. Tree a
Empty Tree a
forall a. Tree a
Empty
x (Branch a
y Tree a
left Tree a
right)
| a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
y = a -> Tree a -> Tree a -> Tree a
forall a. a -> Tree a -> Tree a -> Tree a
Branch a
y (a
x a -> Tree a -> Tree a
forall a. Ord a => a -> Tree a -> Tree a