{-# LANGUAGE DatatypeContexts #-}

-- Binary Search Tree (node valued) examples

-- define a (polymorphic) data-type of a (node-valued) tree
data (Ord a) =>
     Tree a  = Empty
             | Branch a (Tree a) (Tree a)
	     deriving (Show,Read)

-- a function that collects all values from the tree
-- Q: in which order will the leaf nodes appear
-- Exercise: change this to use an infix order
-- Q: what is the property of the list, in infix order, for a binary search tree
fringe                      :: (Ord a) => Tree a -> [a]
fringe Empty                =  []
fringe (Branch x left right)  =  x : (fringe left ++ fringe right) 

-- a simple example: compute the depth of the tree
depth :: (Ord a) => Tree a -> Int
depth Empty = 1
depth (Branch _ left right) = 1 + max (depth left) (depth right)

-- check whether this tree is balanced
isBalanced :: (Ord a) => Tree a -> Bool
isBalanced Empty = True
isBalanced (Branch _ left right) = (abs (depth left - depth right)) <= 1

-- version using higher-order functions
isSorted :: Tree Int -> Bool
isSorted t = and (zipWith (<) xs (tail xs))
             where xs = fringe t

-- overload the == operator on trees
instance (Eq a, Ord a) => Eq (Tree a) where
 Empty          ==  Empty               =  True
 (Branch v1 l1 r1) == (Branch v2 l2 r2) =  (v1==v2) && (l1==l2) && (r1==r2)
 _              ==  _                   =   False

-- insert a new value into a tree, whose leaf values are sorted
-- Q: if the tree is balanced beforehand, will this preserve balanced-ness?
insert :: (Ord a) => Tree a -> a -> Tree a
insert Empty  z = Branch z Empty Empty
insert (Branch x left right) z | null (fringe left)        = Branch x left (insert right z)
                               | maximum (fringe left) < z = Branch x left (insert right z)
                               | otherwise                 = Branch x (insert left z) right  

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

-- build a balanced tree from a list
-- NB: this needs to use insert to generate a search tree
mkTree :: (Ord a) => [a] -> Tree a
mkTree [] = Empty
mkTree xs = mkTree' Empty xs
            	where mkTree' t []     = t
                      mkTree' t (y:ys) = let 
                                             t' = insert t y
                                         in  
                                             mkTree' t' ys

-- sample trees
t1 = Branch 5 (Branch 3 (Branch 2 Empty Empty) (Branch 4 Empty Empty)) (Branch 8 Empty Empty) 
t2 = Branch 1 Empty (Branch 2 Empty (Branch 3 Empty (Branch 4 Empty Empty)))
t10 = mkTree [1..10]