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 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...