# Problem 57

Build a binary search tree from a list. Place lower values the right. By definition, duplicate values are omitted.

## Example

toBSTree [6, 2, 4, 20, 1, 11, 12, 14] ==
Node 6
(Node 2
(Node 1 Empty Empty)
(Node 4 Empty Empty))
(Node 20
(Node 11
Empty
(Node 12
Empty
(Node 14 Empty Empty)))
Empty)

## Unit Test

import Html
import List

type Tree a
= Empty
| Node a (Tree a) (Tree a)

toBSTree : List comparable -> Tree comparable
toBSTree list =
Empty

main =
Html.text
(if (test) then
else
"Your implementation failed at least one test."
)

test : Bool
test =
List.all ((==) True)
[ toBSTree [] == Empty
, toBSTree [1] == Node 1 Empty Empty
, toBSTree [1, 1, 1] == Node 1 Empty Empty
, toBSTree (List.range 1 5) == Node 1 Empty (Node 2 Empty (Node 3 Empty (Node 4 Empty (Node 5 Empty Empty))))
, toBSTree (List.reverse (List.range 1 5)) == Node 5 (Node 4 (Node 3 (Node 2 (Node 1 Empty Empty) Empty) Empty) Empty) Empty
, toBSTree [6, 2, 4, 20, 1, 11, 12, 14, 6] ==
Node 6
(Node 2
(Node 1 Empty Empty)
(Node 4 Empty Empty))
(Node 20
(Node 11
Empty
(Node 12
Empty
(Node 14 Empty Empty)))
Empty)
]

## Hints

1. The solution to Problem 55 can be easily modified to solve this problem.

Solutions