Recall that we had 3 different *styles* of specification for
lists:

- the classical (list = collection of nodes),
- the recursive (list = EMPTY or 2 parts: head and tail (which is
a list))
- ours, which featured operations on
*whole*lists rather than on individual elements (SPLIT and JOIN).

In fact, we have already seen the first two:

- a tree is a collection of nodes in which each node has exactly 1
predecessor (except the
*root*, which has none) and any number of successors (at most N, in the case of an N-ary tree). - a binary tree is either empty or it has 3 parts: a value, a left subtree, and a right subtree.