treesort.hs

module Tree where

data Tree a =
  Leaf
  | Branch (Tree a) a (Tree a)

flatten Leaf = []
flatten (Branch l x r) = (flatten l) ++ [x] ++ (flatten r)

insertOrdered Leaf y = Branch Leaf y Leaf
insertOrdered (Branch l x r) y = case (y < x) of
  True -> Branch (insertOrdered l y) x r
  False -> Branch l x (insertOrdered r y)

treeSort = foldl Leaf insertOrdered