View source for Example:Inductive definition of the set of trees

The set <math>T</math> of [[binary tree]]s 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:

[[Image:tree-defn.svg]]

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

<math>t [[∈]] T [[BNF|::=]] nil [[\mid]] tree(a,t_1,t_2) \qquad a [[∈]] [[ℤ]]</math>

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

[[Image:tree-example.svg]]

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