 Leaf-labelled binary tree

A binary tree with each data label stored at a leaf of a tree. One useful Haskell datatype has constructors One a for a leaf and Two (Tree a) (Tree a) for an internal node. Every finite inhabitant has at least one leaf, so this datatype cannot encode an empty leaf sequence. Its natural tree fold has a leaf operation a -> b and an internal operation b -> b -> b; replacing the two constructors by those operations defines the structural recursion.