Implementing a BST in F#

Bina­ry Search Trees (BST) seem to be a hot top­ic in tech­ni­cal inter­views.

So, in order to help me pre­pare for all these grilling tech­ni­cal tests, I thought I’d give it a crack at imple­ment­ing inser­tion, dele­tion and ver­i­fi­ca­tion log­ic since I’ve already done both breath-first and depth-first tra­ver­sals.

 

Verification

Start­ing with some­thing nice and easy, here’s a func­tion that checks whether a giv­en Tree is a BST. For instance, the fol­low­ing is not a BST as 5 is on the right side of 20 but is less than 20.

     20
    /  \
  10    30
       /  \
      5    40

Here, we start with unbound­ed low­er and upper lim­its (rep­re­sent­ed by None) at the root ele­ment.

Using the ear­li­er tree as exam­ple, as we tra­verse down the right branch of 20, the nodes must be > 20, there­fore the low­er bound is now Some 20. Nodes on the left branch of 30 is also sub­ject to an upper bound of Some 30, nodes on the right branch of 30 will have a high­er low­er bound (now Some 30).

And so on.

 

Insertion

To insert a new node we need to tra­verse down the tree, turn­ing left or right depend­ing on whether the new­Val­ue is < or > the val­ue of the cur­rent node. We repeat this until we either find an emp­ty spot to insert a new node or we find a node with match­ing val­ue (in which case there’s no change to the tree).

 

Deletion

We have left the hard­est for last.

The delete func­tion starts with a sim­i­lar tra­ver­sal log­ic as insert, and where the val­ue is:

  • not found, then do noth­ing
  • only has left child, then replace node with left child
  • only has right child, then replace node with right child

It gets com­pli­cat­ed when the node has both chil­dren, and those chil­dren have their own chil­dren. At that point, you find the in-order pre­de­ces­sor (the right-most leaf of the left branch), replace the cur­rent node’s val­ue with its in-order pre­de­ces­sor, and delete the pre­de­ces­sor.

To walk through it with an exam­ple, sup­pose we have the fol­low­ing tree

       7
     /   \
    3     9
   / \   /  \
  2   5 8   10
     / \
    4   6

Sup­pose we want to delete 7, its in-order pre­de­ces­sor is 6.

We will delete 6 from the left branch.

       7
     /   \
    3     9
   / \   /  \
  2   5 8   10
     /
    4

and then sub­sti­tute the root’s (remem­ber, the node to be delete) val­ue to 6.

       6
     /   \
    3     9
   / \   /  \
  2   5 8   10
     /
    4

and voila!


And now we can trans­late this into code.

I think look­ing back, the match..with clause is a bit ver­bose but also helps make those dif­fer­ent cas­es very clear. Whilst I can per­haps imple­ment it with few­er lines of code, I think the explic­it­ness is a win over clever code that’s hard-to-under­stand.

 

Links