Binary Search Tree in F#

Having a focus on Software Engineering over core Computer Science concepts; my algorithm-fu is not what it should be!

Thankfully there are plenty of books out there and my recent focus on functional programming in F# is helping alleviate that.

This weekend I learned how to build a Binary Search Tree properly in F# using recursion to build "pure functions" demonstrating how this can be done.

What is a Binary Search Tree?

A binary search tree is a data structure designed to allow fast look ups of values. Each value stored is a "leaf" in the tree, stored like this:

         5
       /   \
      4     6
    /   \
   2     3
 /
1

When inserting data into the tree structure; we first check whether the value is less than or greater than the root leaf. If less than, it is passed to left leaf, if greater than it is passed to the right leaf. We keep performing the check down the tree until we can insert the leaf.

For the above tree; the checks would work like so if we were inserting a leaf:

Insert 7 into tree
7 is greater than 5 so pass to the right leaf
7 is greater than 6 so pass to the right leaf 
Right leaf is empty; store 7 here  

When searching the data; we then traverse the tree based on whether the value being searched for is greater than or less than each node. Unlike simply iterating over a list 1 by 1, this operation is faster because it halves the number of items required to search on each iteration. Specifically the search is O(log N) if that means anything to you. There's a nice breakdown of time/space complexity here.

Building the Tree

First we start with a Record Type defining a "leaf" in our tree. Value is what we store, on the leaf, then we have optional left and right sub-leafs to represent that they may or may not be populated.

type Leaf = {value:int; left:Leaf option; right:Leaf option}

We can then build a recursive function to insert a new leaf into the tree. This takes an optional leaf as the root; so when first called with a new tree this will be None.

The function then inserts the leaf in the correct position in the tree; recursing down each branch until an empty space is found.

Note the {t with ...} syntax: this means copy the record type object with these new values. It's syntax sugar allowing us to retain immutability without us having to repopulate the whole record.

let rec insertLeaf (tree:Leaf option) (newValue:int) : Leaf  =
    match tree with 
    | Some t -> if newValue < t.value then {t with left=Some (insertLeaf t.left newValue)}
                else if newValue > t.value then {t with right=Some (insertLeaf t.right newValue)}
                else t
    | None -> {value=newValue; left=None; right=None}

This can now be used to insert a series of values into the tree like so. List.fold allows us to define an accumulator which is passed into each subsequent function, here it is the tree we are building from the values. Initially we pass in None as we have no initial tree.

let tree = [50; 34; 70; 20; 6; 23; 102] 
           |> List.fold (fun acc item -> Some (insertLeaf acc item)) None

Searching the Tree

Searching the tree is very similar to the insert operation, recursively traversing the node until we find a matching value.

let rec searchForLeaf (tree:Leaf option) (searchFor:int) : Leaf option = 
    match tree with 
    | Some t -> if searchFor = t.value then Some t
                else if searchFor < t.value then searchForLeaf t.left searchFor
                else if searchFor > t.value then searchForLeaf t.right searchFor
                else None
    | None -> None

The search can then be used like this:

let returnedLeaf = searchForLeaf tree 6
let missingLeaf = searchForLeaf tree 40

Next steps

This was pretty fun and, once again, shows the power of the F# language when dealing with complex operations (I'd dread trying to write this in C#).

How did I do? Is this a true Binary Search Tree? Are there better approaches? Let me know in the comments.