How to implement a pure tail-recursive insert for BST?

Question

All implementations on insert for BST is non-tail recursive.

Is that possible to write a tail-recursive insert for BST?

If it is possible, how?

Answer 1

It is possible: for example, by writing the insert function in continuation-passing style.

e.g. in Racket

#lang racket

(struct bst-node (left right value) #:transparent)

(define (insert tree new-value)
  (insert-cps tree new-value (lambda (x) x)))

(define (insert-cps tree new-value cont)
  (cond
    [(empty? tree) (cont (bst-node empty empty new-value))]
    [else (match-let ([(bst-node l r v) tree])
            (cond
              [(= v new-value) (cont (bst-node l r v))]
              [(< new-value v) (insert-cps l new-value (lambda (t) (cont (bst-node t r v))))]
              [else (insert-cps r new-value (lambda (t) (cont (bst-node l t v))))]))]))

(insert (insert (insert empty 10) 15) 2)