data Tree a = Nil | Branch (Tree a) a (Tree a) deriving (Eq, Show)

instance Functor Tree where
  fmap _ Nil = Nil
  fmap f (Branch l x r) = Branch (fmap f l) (f x) (fmap f r)

instance Applicative Tree where
  pure f = Branch (pure f) f (pure f)
  (<*>) Nil _ = Nil
  (<*>) _ Nil = Nil
  (<*>) (Branch fl fx fr) (Branch l x r) = Branch (fl <*> l) (fx x) (fr <*> r)