1. (15 points) Induction Consider the following: 
data Tree a = Leaf a | Branch (Tree a) (Tree a) 

reverseTree :: Tree a -> Tree a 
reverseTree (Leaf x) = Leaf x 
reverseTree (Branch left right) = Branch (reverseTree right) (reverseTree left) 

fringe :: Tree a -> [a] 
fringe (Leaf x) = [x] 
fringe (Branch t1 t2) = fringe t1 ++ fringe t2 

Use induction to prove that for any tree t: 
  fringe (reverseTree t) = reverse (fringe t) 

You are allowed to use the following facts about reverse in your proof: 
  reverse (xs ++ ys) = reverse ys ++ reverse xs 
  reverse [x] = [x]