Inorder traversal in Haskell

How many ways can you write a function that performs inorder traversal of a tree? On the whiteboard in my office there is currently five different versions. One has quadratic complexity, one is higher order, one uses an accumulator and three of them needs a helper function to do all the work.

All these variations sprang from a discussion with David Wahlstedt about which versions his termination analysis could handle. It happens that my preferred version of the function, which is linear, first order and doesn't need any accumulator nor a helper function is little more difficult to prove to be terminating. And David's termination analysis cannot handle it.

As a little programming exercise I suggest you try to write my preferred version. To make it a challenge make sure you write it in a functional language. It takes a tree (defined in the obvious way) and returns a list of all the internal node in the order they would be visited by an inorder traversal. Remember, the function must be first order, have linear time complexity with no need for an accumulator or a helper function.