Example:Inductive definition of the set of trees

The set [math]T [/math] of binary trees with integer nodes is defined inductively by

• Rule 1: The empty tree is in [math]T [/math]
• Rule 2: If [math]t_1 [/math] and [math]t_2 [/math] are trees, then the tree with value [math]a [/math], left child [math]t_1 [/math] and right child [math]t_2 [/math] is in T.

We often think of trees pictorially; in this case we might give a BNF definition of [math]T [/math] as follows:

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

[math]t \href{/cs2800/wiki/index.php/%E2%88%88}{∈} T \href{/cs2800/wiki/index.php/BNF}{::=} nil \href{/cs2800/wiki/index.php/%5Cmid}{\mid} tree(a,t_1,t_2) \qquad a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} [/math]

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

Using the second definition, we would write this as [math]tree(3,tree(0,nil,nil),tree(1,tree(0,nil,nil),nil)) [/math]