99 Clojure Problems – 57: Binary Search Trees

Write a function insert-val to add elements to a binary search tree. Then write a function to construct a binary search tree from a list of integer numbers. Then use this function to test the solution of the problem P56.

Example

>(->binary-search-tree 3 2 5 7 1)
[3 [2 [1 nil nil] nil] [5 nil [7 nil nil]]]
>(->binary-search-tree 5, 3, 18, 1, 4, 12, 21)
[5 [3 [1 nil nil] [4 nil nil]] [18 [12 nil nil] [21 nil nil]]]
> (symmetric? *1)
true

Discussion

I feel almost bad about the number of times I have resorted to core.match to solve these problems. Maybe I am just not thinking hard enough about alternative approaches. What it certainly tells us is that pattern matching seems to lend itself very well to this class of problems.

Pattern Match All The Things

Four match clauses seem to do the trick (number three is technically split into two) :

1. Adding nil to a tree is just the tree.
2. Adding a value to nil is a new tree of one node
3. Adding a non-nil value to a non-nil tree: Now it depends on the ordering of the values: is the value greater than the value at the current node: add it to the right subtree, else add it to the left subtree.

What about adding the same value twice? I do not think binary search trees are per se opinionated about how to handle duplicates. In my implementation duplicate values just end up to the right of the value they are identical with. I think it would also be very plausible to make insert-val a no-op if the value is already contained in the tree.

Putting it all together

Constructing the tree seems trivial using the insert-val function we have just constructed. Clojure's reduce is equivalent to a 'fold left' over the input collection. If we reduce the input values with insert-val using nil as the neutral element we get the desired result.

My solution can be found, as always, on Github.

Read more about this series.