-- Binary tree examples

-- define a (polymorphic) data-type of a (leaf-valued) tree
data Tree a  = Leaf a 
             | Branch (Tree a) (Tree a)
	     deriving (Show,Read)

-- a function that collects all values from the tree
fringe                      :: Tree a -> [a]
fringe (Leaf x)             =  [x]
fringe (Branch left right)  =  fringe left ++ fringe right

-- a simple example: compute the depth of the tree
-- depth :: Tree a -> Int
-- depth (Leaf _) = ... -- add code here
-- depth (Branch left right) = ... -- add code here

-- implement a function that checks whether this tree is balanced
-- isBalanced :: Tree a -> Bool


-- implement a function isSorted that checks whether the leaf values are sorted
-- isSorted :: Tree Int -> Bool

-- overload the == operator on trees

-- pretty print a tree, using indentation to represent depth
pp :: (Show a) => Tree a -> IO ()
pp t = mapM_ putStrLn (pp' 0 t)
       where pp' n (Leaf x) = [(take n (repeat ' ')) ++ (show x)]
             pp' n (Branch left right) = [(take n (repeat ' ')) ++ ['.']] ++ pp' (n+1) left ++ pp' (n+1) right


-- build a balanced tree from a list
-- mkTree :: [a] -> Tree a

-- sample trees
t1, t2 :: Tree Int
t1 = Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 3) (Leaf 4))
t2 = Branch (Leaf 1) (Branch (Leaf 2) (Branch (Leaf 3) (Leaf 4)))
-- use mkTree like this
-- t10 :: Tree Int
-- t10 = mkTree [1..10]