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 =
    -- your implementation goes here
    Empty


main =
    Html.text
        (if (test) then
            "Your implementation passed all tests."
         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

Solutions