# Example:Inductive definition of the set of trees

The set of binary trees with integer nodes is defined inductively by

• Rule 1: The empty tree is in
• Rule 2: If and are trees, then the tree with value , left child and right child is in T.

We often think of trees pictorially; in this case we might give a BNF definition of as follows:

However, it is also useful to write trees symbolically; in this case we might define as follows:

Using the first definition, the following is an example tree:

Using the second definition, we would write this as