Inserting a value into a binary search tree in scheme

Question

I'm attempting to create a function that inserts a value into a binary search tree. The conditions within the function seem to work correctly, but I'm not quite sure how to actually insert the value once I reach the null point in the list where it should go.

bst-element refers to another function I have checking if the value already exists in the tree, since the tree should have no duplicates.

(define (bst-insert item bst-tree)
  (cond ((bst-element? item bst-tree)bst-tree)
        ((null? bst-tree) ??? )
        ((< item (bst-value bst-tree))(bst-insert item (bst-left bst-tree)))
        ((> item (bst-value bst-tree))(bst-insert item (bst-right bst-tree)))))

Renzo Renzo · Accepted Answer · 2015-11-01T11:27:52

If you want to insert a value in a tree in a functional way, that is without side-effects, you cannot assume that there is something to do only when you reach the leaf in which you should insert the new value. Rather, you should rebuild the tree while you visit it, so that at the end the result is the new tree with item insert in the right position.

Since you do not show how the tree is implemented, I suppose that an empty tree is represented as '(), and that there exists a function (make-bst item left right) to build a tree with a certain item, a left subtree, and a right subtree. Under these assumptions, here is a possible solution:

(define (bst-insert item bst-tree)
  (cond ((null? bst-tree) (make-bst item '() '()))
        ((= (bst-value bst-tree) item) bst-tree)
        ((< item (bst-value bst-tree))
         (make-bst (bst-value bst-tree)
                   (bst-insert item (bst-left bst-tree))
                   (bst-right bst-tree)))
        (else (make-bst (bst-value bst-tree)
                        (bst-left bst-tree)
                        (bst-insert item (bst-right bst-tree))))))

Note that the check if the item is already present is made inside this function, without the need of duplicating the work with another function.

Inserting a value into a binary search tree in scheme

1 Answers