Advanced data structures

You have learned to use data structures built-in in the FSharp.Core library; now you will learn how to define other advanced data structures on your own in F#.

Binary trees

Binary trees are often used to represent collections of data. For our purpose, a binary tree is an acyclic graph, in which each node has either zero or two children. The top-level node is called the root, and it has no parents, while all other nodes have exactly one parent. A simple way of representing a binary tree is as follows:

    type 'a tree = 
        | Leaf 
        | Node of 'a * 'a tree * 'a tree 

The use of tuples in the Node constructor definition is quite common. We will try to create some objects using this tree in the F# Interactive, as mentioned in the following piece of code:

> Node(1, Leaf, Leaf);; 
val it : int tree = Node (1,Leaf,Leaf) 

This creates an int tree with a top-level root node and empty leaves. As the type definition of 'a tree is recursive...