Ordered Trees: when the order of subtrees is significant.


Unordered: maybe a family tree.

Ordered: maybe left child comes before right child in alphabetical order.

Structural definition of binary trees: a binary tree is either empty or its has 3 parts:

Properties of recursive data structures can usually be computed in a recursive manner that mirrors their definition.

int size (binary_tree *t)
{ return is_empty(t) ? 0
         : 1 + size(t->left) + size(t->right); }