My friend Kototama and I are both learning functional languages, and exchanging / comparing code for some classical algorithms. The last to date is an insertion in a binary search tree (BST).

The most intuitive algorithm is recursive, but not *tail-recursive*. One cannot assume a BST to be balanced, and it behaves as a simply linked list in the worst case. Having a tail-recursive algorithm will guarantee the insertion, even in a very deep tree.

*Example of tail recursion*

The data structure is quite simple: A BST containing elements of type *a* is either an empty leaf (Nil) or a Node with 3 items: an element of type *a* (elt), and 2 sub-nodes which are BSTs containing *a*s: l for *left* and r for *right*.

data Bst a = Nil | Node {

elt :: a,

l :: Bst a,

r :: Bst a} deriving Show

#### Intuitive algorithm

insert_ntr Nil x = Node x Nil Nil

insert_ntr n x | x < elt n = n {l = insert_ntr (l n) x}

insert_ntr n x | x > elt n = n {r = insert_ntr (r n) x}

insert_ntr n x | otherwise = n

The second line tells us that inserting x in n if x < n is the same node n with its left branch equal to the insertion of x in the left of n.

Let’s take the numbers 4,3,1,2 and insert them in a BST of integers, with a root equal to Nil.

- insert Nil 4 → this gives us a new root
- insert (Node 4 Nil Nil) 3 → this inserts 3 under 4 on the left.
- insert (Node 4 (Node 3 Nil Nil) Nil) 1 → this inserts 1 under 3 on the left.
- insert (Node 4 (Node 3 (Node 1 Nil Nil) Nil) Nil) 2 → this inserts 2 under 1 on the right.

The resulting tree is the following:

Node {elt = 4, l = Node {elt = 3, l = Node {elt = 1, l = Nil,

r = Node {elt = 2, l = Nil, r = Nil}}, r = Nil}, r = Nil}

#### Tail-recursive algorithm

Suppose we already have 3 of the previous nodes (4,3,1), and want to insert our final element, the number 2. We know that 2 is going to the left of 4, but where exactly is not known yet. So in effect, the root node is a function of its left branch. It is a function that takes a tree (not sure what it is yet), attaches it to the left of number 4, keeps the right branch intact, and returns the whole thing as a root.

In turn, this left branch is the number 3, with nothing to its right and something that is going to change to its left, since 2 < 3. So the node 3 is a function of its left branch.

We go like this all the way to the node with 1, which is a function of its right branch.

- root = λ a → Node 4 a Nil
- a = λ b → Node 3 b Nil
- b = λ c → Node 1 Nil c
- c = Node 2 Nil Nil

So there we have the general algorithm: if we compose these functions, we get a complete root The key is to consider the root as a function of one of its branch, which is in turn a function of one of its branch, etc. By composing those functions step by step, we create a root as a function of the node to insert, which is done at the leaf level. The first function is composed with *id*, which is the *identity function*.

The last step is to attach the new leaf:

root = (λ c → (Node 4 (Node 3 (Node 1 Nil c) Nil) Nil) (Node 2 Nil Nil)

root = (Node 4 (Node 3 (Node 1 Nil (Node 2 Nil Nil)) Nil) Nil)

**In Haskell:**

insert n x = recur n x id where recur Nil x fun = fun $ Node x Nil Nil recur n x fun | x < elt n = recur (l n) x $ fun . (\k -> n {l = k}) recur n x fun | x > elt n = recur (r n) x $ fun . (\k -> n {r = k}) recur n x fun | otherwise = n

The whole code is on github’s gist; I find it very beautiful.