Binary Trees

Recursive datatype definition

A binary tree is a recursive datatype where each node is either empty or holds a label and two subtrees:

type 'a tree =
  Lf
| Br of 'a * 'a tree * 'a tree

• Lf (leaf) represents an empty tree.
• Br(v, t1, t2) is a branch node with label v, left subtree t1, and right subtree t2.
• The type parameter 'a makes it polymorphic: an int tree stores integers, a string tree stores strings, etc.

Constructing a tree

Br(1, Br(2, Br(4, Lf, Lf),
             Br(5, Lf, Lf)),
       Br(3, Lf, Lf))

This builds a tree with root label 1, left child 2 (with children 4 and 5), and right child 3. All leaves are Lf.

Lists as a recursive datatype

Built-in OCaml lists could be declared as a user-defined type:

type 'a mylist =
  Nil
| Cons of 'a * 'a mylist

This mirrors the built-in [] and :: exactly. The only thing not reproducible is the [a; b; c] syntactic sugar, which is part of the OCaml grammar.

Other recursive datatypes

Not all datatypes need to be both recursive and polymorphic:

Type	Recursive?	Polymorphic?	Example
'a tree	Yes	Yes	Binary trees with arbitrary labels
shape	Yes	No	Null | Join of shape * shape
'a option	No	Yes	None | Some of 'a

A shape value represents the structure of a binary tree with no data attached. The option type is polymorphic (useful for any type) but not recursive (it does not contain further options).