What should a Traversable instance look like for a Tree datatype with a nested Maybe value?

I have a Haskell exam in three days, so I thought I should practice a little and pulled up past exams, one of which features the following Tree datatype:

data Tree a = Leaf1 a | Leaf2 a a | Node (Tree a) (Maybe (Tree a)) deriving (Eq, Ord, Show)

It didn't seem that challenging at first, but then I realized I have to write a Traversable instance for this Tree. Dealing with the leaves were easy enough:

instance Traversable Tree where
  traverse f (Leaf1 a)   = Leaf1 <$> f a
  traverse f (Leaf2 a b) = Leaf2 <$> f a <*> f b

However, I started running into problems with the Node.

  traverse f (Node t Nothing)  = Node <$> traverse f t <*> Nothing
  traverse f (Node l (Just r)) = Node <$> traverse f l <*> Just (traverse f r)

Naturally, these don't work, and I can't wrap my head around what should come after the second <*>. I tried using holes, but the messages given to me by ghci didn't help much (I get that the problem is with types, but I have no idea how I'm supposed to fix it).

Here's the error message I got when I tried to compile it:

* Couldn't match type `f' with `Maybe'
  `f' is a rigid type variable bound by
    the type signature for:
      traverse :: forall (f :: * -> *) a b.
                  Applicative f =>
                  (a -> f b) -> Tree a -> f (Tree b)
    at exam.hs:92:3-10
  Expected type: f (Maybe (Tree b))
    Actual type: Maybe (Maybe (Tree b))
* In the second argument of `(<*>)', namely `Nothing'
  In the expression: Node <$> traverse f t <*> Nothing
  In an equation for `traverse':
      traverse f (Node t Nothing) = Node <$> traverse f t <*> Nothing
* Relevant bindings include
    f :: a -> f b (bound at exam.hs:94:12)
    traverse :: (a -> f b) -> Tree a -> f (Tree b)
      (bound at exam.hs:92:3)
   |
94 |   traverse f (Node t Nothing)  = Node <$> traverse f t <*> Nothing
   |                                                            ^^^^^^^

Could someone please give me some pointers or a possible fix for this issue?

Solution

traverse lets you apply a "function with an effect" to every "slot" of a data structure, maintaining the structure's shape. It has the type:

traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

It relies crucially on the fact that the type of the "effects" is an Applicative. What operations does Applicatve provide?

it lets us lift pure functions and apply them to effectful actions with <$>.
it lets us combine effectful actions with (<*>) :: f (a -> b) -> f a -> f b. Notice that the second parameter is an effectful action, not a pure value.
it lets us take any pure value and put it in an effectful context, using pure :: a -> f a.

Now, when the node has a Nothing, there's no effect to perform because there aren't any values, but the <*> still requires an effectful action on the right. We can use pure Nothing to make the types fit.

When the node has a Just t, we can traverse the subtree t of type Tree a with the function a -> f b and end up with an action f (Tree b). But the <*> is actually expecting an f (Maybe (Tree b)). The lifted Node constructor makes us expect that. What can we do?

The solution is to lift the Just constructor into the action using <$>, which is another name for fmap.

Notice that we haven't changed the overall "shape" of the value: the Nothing is still Nothing, the Just is still Just. The structure of the subtrees didn't change either: we traversed them recursively but didn't modify them otherwise.