How does this binary tree code represent a tree?

Question

I was reading through past papers for my University's Haskell exam and came across a question involving trees where the tree type was implemented as such:

data Tree a = Lf a                  -- leaf
            | Tree a :+: Tree a     -- branch

It then goes on to outline an example tree that could be used with various functions, for example:

((Lf 1 :+: Lf 2) :+: (Lf 3 :+: Lf 4))

My confusion with this code is how it can represent a tree without having some notion of a root element. My intuition would suggest the tree being represented here would look like this:

  / \
/ \ / \
1 2 3 4

but such a tree would possess no root elements, only leaves, which certainly seems wrong to me. How is a tree actually expressed in this code?

Answer 1

It is a tree with data stored only in the leaves. There is no requirement that a tree have data in the interior nodes, although of course many algorithms can only operate on a tree with data in its interior nodes (e.g. BST search).

You might ask in what situation such a structure is useful. Consider Huffman decoding, where no data is needed in the interior nodes. You simply traverse down the tree, moving left on 0 and right on 1, until you reach a leaf node, at which point you have decoded a character.