A Universe of Sorts

The catalan numbers $C_n$ count the number of binary trees on $n$ nodes.
For every binary tree, label the nodes in some standard ordering (eg. BFS).
Pick the lex smallest unbalanced node (node with different left and right subtree sizes).
The operation that swaps the left and right subtrees of the lex smallest unbalanced node is an involution.
This operation only fails when we have a complete binary tree, so the number of nodes is $n = 2^r - 1$ , so we pair such a complete binary tree to itself.
This breaks the set $C_n$ into an even number of trees (pairs of unbalanced trees) and a potential "loner tree" (paired with itself) which is the complete binary tree.
Thus $C_n$ is odd iff $n = 2^r - 1$ , which allows for us to have a complete binary tree, which is not paired by the involution.
Reference

§ When Are the Catalan Numbers Odd