Problem 57 Solutions

Solution 1

Add one node at a time.

toBSTree : List comparable -> Tree comparable
toBSTree list =
    case list of
        [] -> 
            Empty 

        _ -> 
            List.foldl addBSNode Empty list


addBSNode : comparable -> Tree comparable -> Tree comparable
addBSNode v tree =
    case tree of
        Empty ->
            Node v Empty Empty

        Node v_ left right ->
            if v > v_ then
                Node v_ left (addBSNode v right)
            else if v < v_ then
                Node v_ (addBSNode v left) right 
            else
                tree

Solution 2

Here's an modification using Basics.compare.

toBSTree : List comparable -> Tree comparable
toBSTree list =
    case list of
        [] -> 
            Empty 

        _ -> 
            List.foldl addBSNode Empty list


addBSNode : comparable -> Tree comparable -> Tree comparable
addBSNode v tree =
    case tree of
        Empty ->
            Node v Empty Empty

        Node v_ left right ->
            case compare v v_ of 
                GT ->
                    Node v_ left (addBSNode v right)

                LT -> 
                    Node v_ (addBSNode v left) right       

                EQ -> 
                    tree

Back to problem