Lambda the Ultimate

After reading the thread about PL puzzles I decided for a change to design my own puzzle instead of my own PL.

How about this - "mirror an immutable binary tree preserving existing sharing"?

So in Haskell, I would take this data type:

data Tree = Leaf | Node Tree Tree

and write a function that maps leaves to leaves, and nodes to nodes with swapped children.
"mirror an immutable binary tree" was easy. What about "preserving existing sharing"?
For that I need to cheat a bit and augment my data type with identifiers, and pretend that meets the requirements of the puzzle.

Or I may use StableName, but then I will end up inside IO kitchen sink.
One may argue that ability to recognize sharing is not referentially transparent, and therefore it's a feature that it's available only inside IO computations. I however feel that this binary choice between purity and impurity is too harsh - can I have an indulgence, please?

To be constructive, I decided to redesign the puzzle so it is a fair game.
Now it sounds as: "clone an immutable binary tree obtaining maximum sharing".
I believe that while pure code cannot recognize sharing, it can at least manifest its desire to create sharing (subject to compiler's whim, of course).

The full tree of depth n (having 2ⁿ-1 nodes) will therefore be compressed to a DAG of n nodes - impressive ratio!

Additional points if your code does not create intermediate structures (this is unfair towards PLs without implicit stack, BTW), if it traverses the original tree only once, if it can be reused for other data types, and if you can state it's computational complexity and/or maximum size of the stack (sure, some of these tasks are much harder than others).

Matching Objects With Patterns. Burak Emir, Martin Odersky, and John Williams.

Data in object-oriented programming is organized in a hierarchy of classes. The problem of object-oriented pattern matching is how to explore this hierarchy from the outside. This usually involves classifying objects by their run-time type, accessing their members, or determining some other characteristic of a group of objects. In this paper we compare six different pattern matching techniques: object-oriented decomposition, visitors, type-tests/typecasts, typecase, case classes, and extractors. The techniques are compared on nine criteria related to conciseness, maintainability and performance. The paper introduces case classes and extractors as two new pattern-matching methods and shows that their combination works well for all of the established criteria.