Implementing a BST in F#

Yan Cui

I help clients go faster for less using serverless technologies.

Table of Content

Verification

Insertion

Deletion

Links

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.

	open System

	type Tree<'a> =
	\| Empty
	\| Node of value: 'a * left: Tree<'a> * right: Tree<'a>

	let isBST (tree : Tree<'a>) =
	let rec verify lo hi tree =
	match tree with
	\| Empty -> true
	\| Node (value, left, right) ->
	match lo, hi with
	\| Some lo, _ when value < lo -> false
	\| _, Some hi when value > hi -> false
	\| _ ->
	let hi' = defaultArg hi value \|> min value \|> Some
	let lo' = defaultArg lo value \|> max value \|> Some
	verify lo hi' left && verify lo' hi right

	verify None None tree

	// usage
	let tree1 =
	Node (1, Empty, Empty)

	let tree2 =
	Node (7,
	Node (3, Empty, Empty),
	Node (9, Empty, Empty))

	let tree3 =
	Node (20,
	Node (10, Empty, Empty),
	Node (30,
	Node (5, Empty, Empty),
	Node (40, Empty, Empty)))

	let tree4 =
	Node ('a', Empty, Empty)

	let tree5 =
	Node ('b',
	Node ('a', Empty, Empty),
	Node ('c', Empty, Empty))

	let tree6 =
	Node ('c',
	Node ('b', Empty, Empty),
	Node ('d',
	Node ('a', Empty, Empty),
	Node ('e', Empty, Empty)))

	isBST tree1 // true
	isBST tree2 // true
	isBST tree3 // false

	isBST tree4 // true
	isBST tree5 // true
	isBST tree6 // false

view raw verify-bst.fsx hosted with

by GitHub

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).

	let rec insert newValue (tree : Tree<'a>) =
	match tree with
	\| Empty -> Node (newValue, Empty, Empty)
	\| Node (value, left, right) when newValue < value ->
	let left' = insert newValue left
	Node (value, left', right)
	\| Node (value, left, right) when newValue > value ->
	let right' = insert newValue right
	Node (value, left, right')
	\| _ -> tree

	// usage
	Empty
	\|> insert 2
	\|> insert 1
	\|> insert 5
	\|> insert 4

	// 1
	// / \
	// 2 5
	// /
	// 4

view raw insertion-bst.fsx hosted with

by GitHub

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.

	let rec findInOrderPredecessor (tree : Tree<'a>) =
	match tree with
	\| Empty -> Empty
	\| Node (_, _, Empty) -> tree
	\| Node (_, _, right) -> findInOrderPredecessor right

	let rec delete value (tree : Tree<'a>) =
	match tree with
	\| Empty -> Empty
	\| Node (value', left, right) when value < value' ->
	let left' = delete value left
	Node (value', left', right)
	\| Node (value', left, right) when value > value' ->
	let right' = delete value right
	Node (value', left, right')
	\| Node (_, Empty, Empty) ->
	Empty
	\| Node (_, left, Empty) ->
	left
	\| Node (_, Empty, right) ->
	right
	\| Node (_, left, right) ->
	let (Node(value', _, _)) = findInOrderPredecessor left
	let left' = delete value' left
	Node (value', left', right)

	// usage
	let tree7 =
	Node (7,
	Node (3,
	Node (2, Empty, Empty),
	Node (5,
	Node (4, Empty, Empty),
	Node (6, Empty, Empty))),
	Node (9,
	Node (8, Empty, Empty),
	Node (10, Empty, Empty)))

	delete 7 tree7

view raw deletion-bst.fsx hosted with

by GitHub

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.

Verification

Insertion

Deletion

Links

Leave a Comment