Insert in binary search tree in tail recursive

Learning
1

Hello guys , So I’ve made a function to insert in a binary search tree which is
type 'a tree = Empty | Bin of 'a * 'a tree * 'a tree :

let rec bst_insert t x =
  match t with
  |Empty-> Bin((x,1),Empty,Empty)
  |Bin((key,multiplicity),left,right)
    -> if key=x then Bin((key,multiplicity+1),left,right) 
       else if key>x then Bin((key,multiplicity),bst_insert left x , right) 
       else Bin((key,multiplicity),left,bst_insert right x)

And I would like to transform it into a tail recursive function since Bin ( …) is copy into the stack .
But I’ve no idea on how to go for it , do you have a clew for me ?

2

A clue for this kind of problem is that non-tail recursive functions implictely put some data on the stack. To transform a non-tail recursive function is then a question of isolating this implicit data and making it an explicit argument of the recursive function.

Here the implicit data can be summed up to “how to reconstruct the full tree from the subtree that the function is currently exploring”. A possible first step is to notice that the previous wording describes a function that maps subtree to tree. In other words, this implicit data can be expressed as a function 'a tree -> 'a tree, which suggests to start with

let rec bst_insert tree x current_subtree_to_full_tree_function = …
1 Like
3

If this is not an exercise I’d like to point out that insertion into a tree should not reach a depth that is problematic in terms of stack size provided the tree is kept balanced. I therefore would pay more attention to balancing-tree algorithms than to tail recursion.

A nice algorithm is this one: https://twitter.com/b0rk/status/906367594441138176

1 Like
4

Ochatron : I’ll try this way if I can find how to implement this function , thanks you ! :grinning:

5

lindig : I really like the algorithm you send me , my exercice isn’t to transform insert in tail recursive , I was just seeking a better way to implement it ( with less cost ) cause after we must use our function insert to implement
bst_from_list : 'a list -> ('a * int) tree .
Thanks to you two guys , I’ll try both ways :blush:

(sorry for broken english)

6

I had pointed out the algorithm mainly because it is randomised and this makes it interesting. You might want to take a look at deterministic balanced-tree implementations. The classic work is the thesis (freely available) by Chris Okasaki and his book “Purely functional data structures”.

2 Likes