3. Tree Specification

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

  1. the classical (list = collection of nodes),

  2. the recursive (list = EMPTY or 2 parts: head and tail (which is a list))

  3. ours, which featured operations on whole lists rather than on individual elements (SPLIT and JOIN).
Specifications for trees can be viewed as generalizations of list specifications - a list is a degenerate kind of tree - so it is no surprise that tree specifications also fall into these three categories.

In fact, we have already seen the first two:

  1. 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).

  2. a binary tree is either empty or it has 3 parts: a value, a left subtree, and a right subtree.