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 | node of '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.
fun nodes (empty) = 0 | nodes (node (_, t1, t2)) = 1 + nodes t1 + nodes t2;
Definition (Path)
A path (from tree t1 to its subtree tk) is the list t1, t2, ... tk of trees where, for all 0 < i < k, either ti = node (n, ti+1, t') or ti = node (n, t', ti+1).
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.
fun maxdepth (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.