Structural Definition of Binary Trees

A binary tree is either empty or it has 3 parts:

• a value
• a left subtree
• a right subtree

Whenever a data structure has a recursive definition like this, most of the `properties' of the data structure can be computed in a recursive manner which exactly mirrors the definition.

For example, here is a function to compute the number of nodes in a binary tree:

        int size(binary_tree *t)

        {

          return is_empty(t) ? 0 : 1 + size(t->left) + size(t->right);

        }

With lists we had an alternative to recursion - we could scan through a list as easily with normal loops (while, do ... while) as with recursion. This is not true for trees. It is possible to scan through a tree non-recursively, but it is not nearly as easy as scanning recursively.