trees.hs

data Tree a = EmptyTree
            | Node a (Tree a) (Tree a)
            deriving (Eq, Ord, Show)


simpleTree :: Tree Int
simpleTree = Node 1 (Node 2 EmptyTree EmptyTree)
                    (Node 3 EmptyTree EmptyTree)

tree1 :: Tree Int
tree1 = foldr insert EmptyTree [3, 93, 5, 7, 23, 4, 8, 56, 43]

example :: Tree Char
example = Node 'F'
                (Node 'B'
                 (Node 'A' EmptyTree EmptyTree)
                 (Node 'D' (Node 'C' EmptyTree EmptyTree)
                           (Node 'E' EmptyTree EmptyTree)))
                (Node 'G'
                 EmptyTree
                 (Node 'I'
                  (Node 'H' EmptyTree EmptyTree)
                  EmptyTree))

sizeEmpty :: Tree a -> Int
sizeEmpty EmptyTree    = 1
sizeEmpty (Node a l r) = sizeEmpty l + sizeEmpty r

size :: Tree a -> Int
size EmptyTree = 0
size (Node x l r) = 1 + size l + size r

insert :: Ord a => a -> Tree a -> Tree a
insert x EmptyTree = Node x EmptyTree EmptyTree
insert x (Node a l r)
  | x == a = Node x l r
  | x <  a = Node a (insert x l) r
  | x >  a = Node a l (insert x r)

preOrder :: Show a => Tree a -> [a]
preOrder EmptyTree = []
preOrder (Node x l r) = [x] ++ (preOrder l) ++ (preOrder r)

postOrder :: Show a => Tree a -> [a]
postOrder EmptyTree = []
postOrder (Node x l r) = (postOrder l) ++ (postOrder r) ++ [x]

inOrder :: Show a => Tree a -> [a]
inOrder EmptyTree    = []
inOrder (Node x l r) = (inOrder l) ++ [x] ++ (inOrder r)

levelOrder :: (Eq a, Show a) => Tree a -> [a]
levelOrder EmptyTree   = []
levelOrder t           = levelOrder' [t] []
  where levelOrder' []                acc = reverse acc
        levelOrder' ((Node x l r):ts) acc =
          levelOrder' (ts ++ filter (/= EmptyTree) [l, r]) (x : acc)
main = do
    print $ "Pre-order: " ++ preOrder example
    print $ "In-order: "  ++ inOrder example
    print $ "Post-order: " ++ postOrder example
    print $ "Level-order: " ++ levelOrder example