Implementing a BST in F#

You can become a serverless blackbelt. Enrol to my 4-week online workshop Production-Ready Serverless and gain hands-on experience building something from scratch using serverless technologies. At the end of the workshop, you should have a broader view of the challenges you will face as your serverless architecture matures and expands. You should also have a firm grasp on when serverless is a good fit for your system as well as common pitfalls you need to avoid. Sign up now and get 15% discount with the code yanprs15!

Binary Search Trees (BST) seem to be a hot topic in technical interviews.

So, in order to help me prepare for all these grilling technical tests, I thought I’d give it a crack at implementing insertion, deletion and verification logic since I’ve already done both breath-first and depth-first traversals.

 

Verification

Starting with something nice and easy, here’s a function that checks whether a given Tree is a BST. For instance, the following 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 unbounded lower and upper limits (represented by None) at the root element.

Using the earlier tree as example, as we traverse down the right branch of 20, the nodes must be > 20, therefore the lower bound is now Some 20. Nodes on the left branch of 30 is also subject to an upper bound of Some 30, nodes on the right branch of 30 will have a higher lower bound (now Some 30).

And so on.

 

Insertion

To insert a new node we need to traverse down the tree, turning left or right depending on whether the newValue is < or > the value of the current node. We repeat this until we either find an empty spot to insert a new node or we find a node with matching value (in which case there’s no change to the tree).

 

Deletion

We have left the hardest for last.

The delete function starts with a similar traversal logic as insert, and where the value is:

  • not found, then do nothing
  • only has left child, then replace node with left child
  • only has right child, then replace node with right child

It gets complicated when the node has both children, and those children have their own children. At that point, you find the in-order predecessor (the right-most leaf of the left branch), replace the current node’s value with its in-order predecessor, and delete the predecessor.

To walk through it with an example, suppose we have the following tree

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

Suppose we want to delete 7, its in-order predecessor is 6.

We will delete 6 from the left branch.

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

and then substitute the root’s (remember, the node to be delete) value to 6.

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

and voila!

And now we can translate this into code.

I think looking back, the match..with clause is a bit verbose but also helps make those different cases very clear. Whilst I can perhaps implement it with fewer lines of code, I think the explicitness is a win over clever code that’s hard-to-understand.

 

Links

Liked this article? Support me on Patreon and get direct help from me via a private Slack channel or 1-2-1 mentoring.
Subscribe to my newsletter


Hi, I’m Yan. I’m an AWS Serverless Hero and I help companies go faster for less by adopting serverless technologies successfully.

Are you struggling with serverless or need guidance on best practices? Do you want someone to review your architecture and help you avoid costly mistakes down the line? Whatever the case, I’m here to help.

Hire me.


Skill up your serverless game with this hands-on workshop.

My 4-week Production-Ready Serverless online workshop is back!

This course takes you through building a production-ready serverless web application from testing, deployment, security, all the way through to observability. The motivation for this course is to give you hands-on experience building something with serverless technologies while giving you a broader view of the challenges you will face as the architecture matures and expands.

We will start at the basics and give you a firm introduction to Lambda and all the relevant concepts and service features (including the latest announcements in 2020). And then gradually ramping up and cover a wide array of topics such as API security, testing strategies, CI/CD, secret management, and operational best practices for monitoring and troubleshooting.

If you enrol now you can also get 15% OFF with the promo code “yanprs15”.

Enrol now and SAVE 15%.


Check out my new podcast Real-World Serverless where I talk with engineers who are building amazing things with serverless technologies and discuss the real-world use cases and challenges they face. If you’re interested in what people are actually doing with serverless and what it’s really like to be working with serverless day-to-day, then this is the podcast for you.


Check out my new course, Learn you some Lambda best practice for great good! In this course, you will learn best practices for working with AWS Lambda in terms of performance, cost, security, scalability, resilience and observability. We will also cover latest features from re:Invent 2019 such as Provisioned Concurrency and Lambda Destinations. Enrol now and start learning!


Check out my video course, Complete Guide to AWS Step Functions. In this course, we’ll cover everything you need to know to use AWS Step Functions service effectively. There is something for everyone from beginners to more advanced users looking for design patterns and best practices. Enrol now and start learning!