I actually like the first one best, and would prefer a case-lambda even more. Once it becomes available we can write

  foo x y = x >>= \case
    Leaf -> ..
    Branch l r -> ..

modulo whatever syntax gets chosen. That would save an unnecessary temporary variable. (See https://groups.google.com/group/haskell-cafe/browse_thread/t...)

Temporary variables clutter up the name space. While reading code you have to look for shadowing, or whether that variable is ever used again.