We will introduce a few important definitions for trees as defined by the parameterised tree datatype which was given earlier [*]. To recap, it is this:

datatype'a tree = empty | nodeof'a * 'a tree * 'a tree;

**Definition (Nodes)**

The nodes of an 'a tree are the values of type 'a which it contains. We can easily define a function which counts the number of nodes in a tree.

funnodes (empty) = 0 | nodes (node (_, t1, t2)) = 1 + nodes t1 + nodes t2;

**Definition (Path)**

A *path* (from tree *t _{1}* to its subtree

**Definition (Leaf)**

A tree *t* is a *leaf* if it has the form
node (*n*, empty, empty).

**Definition (Depth)**

We will now describe two Standard ML functions which calculate the depth of a tree. They both have type 'a tree -> int.

funmaxdepth (empty) = 0 | maxdepth (node (_, t1, t2)) = 1 + Int.max (maxdepth t1, maxdepth t2);

Above, Int.max is the integer maximum function. The mindepth function just uses Int.min instead of Int.max.

**Definition (Perfectly balanced)**

A tree *t* is perfectly balanced if its
maximum and minimum depths are equal.