----------------------------------------------ADT module
module Searchtree(STree, listToSTree, sTreeToList) where

data Ord a => STree a = Node a (STree a) (STree a) | Nil

insertSTree :: Ord a => a -> STree a -> STree a
insertSTree x Nil = Node x Nil Nil
insertSTree x (Node y left right)
   | x<=y       = Node y (insertSTree x left) right
   | otherwise  = Node y left (insertSTree x right)

listToSTree :: Ord a => [a] -> STree a
listToSTree = foldr insertSTree Nil

sTreeToList :: Ord a => STree a -> [a]
sTreeToList Nil = []
sTreeToList (Node x left right)
   = (sTreeToList left) ++ [x] ++ (sTreeToList right)