A simple Binary Search Tree in F#.

BinarySearchTree.fs

module BinarySearchTree

// Recursive tree type.
// Generic constraint to prevent creation of
// a tree where it doesn't make sense.
type Tree<'a when 'a : comparison> =
    | Node of 'a * Tree<'a> * Tree<'a>
    | Empty

/// Create an empty tree.
let createEmptyTree = Empty

/// Create a tree with a single value.
let createTree value = Node (value, Empty, Empty)

/// Insert a value into the given tree.
let rec insert tree value = 
    match tree with
    | Empty -> Node (value, Empty, Empty)
    | Node (node, lhs, rhs) when value < node -> 
        Node (node, insert lhs value, rhs)
    | Node (node, lhs, rhs) when value > node -> 
        Node (node, lhs, insert rhs value)
    | _ -> tree

/// Does the tree contain the value?
let rec contains tree value =
    match tree with
    | Empty -> false
    | Node (node, lhs, rhs) ->
        if node = value then true
        else if value < node then contains lhs value
        else contains rhs value

/// Convert a list to a binary search tree.
let toBST list = 
    let mutable tree = createEmptyTree

    let rec insertFirstElement list =
        match list with
        | head :: tail ->
            tree <- insert tree head
            insertFirstElement tail
        | [] -> ()

    insertFirstElement list
    tree

/// Get the largest value in the given tree.
let rec largest tree = 
    match tree with
    | Empty -> None
    | Node (node, _, rhs) -> 
        match rhs with
        | Empty -> Some node
        | _ -> largest rhs

/// Get the smallest value in the given tree.
let rec smallest tree = 
    match tree with
    | Empty -> None
    | Node (node, lhs, _) -> 
        match lhs with
        | Empty -> Some node
        | _ -> smallest lhs