The binary search tree

One of the most popular forms of trees in computer science is the binary tree. As the name indicates, a binary tree is a tree in which every node has either zero, one or, at the most, two child nodes. A binary tree is also sometimes referred to as a binary search tree; however, they are different as we show you next.

For example, you can see a binary tree in the diagram that follows, a tree where every node has at most two children:

In a binary search tree, the left child node contains only the nodes with values which are less than the parent node. Similarly, the right child node can only contain nodes with values greater than or equal to the parent node as shown in the following figure:

In F#, there are various ways of representing a binary tree. For example, a discriminated union-based binary tree of strings can be written as follows:

type tree = 
  |Leaf of string 
  |Node of tree * tree

And a generic version can be as follows:

type tree<'a> = 
  |Leaf of 'a
  ...