Yan Cui

I help clients go faster for less using serverless technologies.

**Table of Content**

**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

*, nodes on the right branch of 30 will have a higher lower bound (now*

**Some 30***).*

**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

*, and where the value is:*

**insert**- 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

- Wikipedia entry
- Breath-First Traversal
- Depth-First Traversal
- All my Project Euler solutions in F#
- All my Advent of Code solutions in F#

**Whenever you’re ready, here are 4 ways I can help you:**

**Production-Ready Serverless**: Join 20+ AWS Heroes & Community Builders and 1000+ other students in levelling up your serverless game. This is your one-stop shop for**quickly levelling up your serverless skills**.- Do you want to know
**how to test serverless architectures**with a fast dev & test loop? Check out my latest course,**Testing Serverless Architectures**and learn the smart way to test serverless. - I help clients
**launch product ideas**,**improve their development processes**and**upskill their teams**. If you’d like to work together, then let’s**get in touch**. **Join my community on Discord**, ask questions, and join the discussion on all things AWS and Serverless.