# Binary Search Trees in Clojure

This weekend I was able to spend some more time exploring Clojure. I decided that it would be interesting to reimplement some of the Binary Search Tree work I had previously done in PHP. We start by creating a simple record definition which describes the contents of a Node.

## Insertion

Using this Node record, we are able to now construct an insertion function which uses Clojure’s parameter deconstruction to great effect. Using the `cond` macro helps document an extremely succinct algorithm for inserting a new node into a provided tree.

## Removal

Removing a given value from the tree requires a little more work than its’ insertion counterpart. However, `cond` (again) allows us to clearly document these actions, handling the three different states the given values Node could be in. Note that the third state requires the use of the followingly documented `min` function.

## Minimum and Maximum Value

As a Binary Search Tree’s invariant is for every Nodes left branch to be less, and right branch to be greater, we can implement simple functions which return the minimum and maximum values present in the tree.

## Contains

Following a similar traversal pattern found in the insertion algorithm we are able to check if a given value is present in the tree using the following function.

## Count and Height

Statistical analysis on the created tree can be carried out in the form of checking the height of the tree (depth), along with the total Node count.

## Asserting the Invariant

We are able to assert that the given tree maintains the invariance required to be a BST by using the following function.

## Creating and Displaying the Tree

Using the following function we are able to create a new tree from a supplied sequence - which uses a `reduce` to insert each value into the tree, building up the final result along the way.

There are many ways to concatenate sequences within Clojure, however, I feel that the approach below clearly expresses the desired intent. Using a combination of ‘syntax-quote’ and ‘unquote-splicing’ we are able to build up a list of the supplied tree’s contents.

## Example

Finally, we are able to use all these functions in a contrived example, highlighting each of them in action.