Inserting into a Binary Tree in Scheme

Question

I am wondering how to insert elements from a list into a binary search tree. I am wondering why the following code does not work as I expected. The output is '((4 1 5 13 6) () ()) My next problem is going to be sorting the elements in the list, but for now I just want to insert them.

Is my output correct for the problem I stated? My code is as follows:

( define ( make-tree value left right ) 
( list value left right ))
( define ( value tree ) ( car tree ))
( define ( left tree ) ( cadr tree ))
( define ( right tree ) ( caddr tree ))

(define (insert-list L T)
 (cond ((null? T) (make-tree L '() '()))
    ((= (car L) (value T)) T)
    ((< (car L) (value T)) (make-tree (value T)
                                      (insert-list (car L) (left T))
                                      (right T)))
    ((> (car L) (value T)) (make-tree (value T)
                                      (left T)
                                      (insert-list (car L) (right T))))))

Answer 1

The problem with this code

When writing recursive code, it's typically a good idea to consider what the function is supposed to take as arguments, and what it should return, as well as what the base case is.

(define (insert-list L T)
 (cond
    ((null? T) (make-tree L '() '()))                                     ; case 1
    ((= (car L) (value T)) T)                                             ; case 2
    ((< (car L) (value T)) (make-tree (value T)                           ; case 3
                                      (insert-list (car L) (left T))
                                      (right T)))
    ((> (car L) (value T)) (make-tree (value T)                           ; case 4
                                      (left T)
                                      (insert-list (car L) (right T))))))

Based on your description, insert-list is supposed to take a list of elements and a tree, and return the tree that you'd get from inserting those elements into the tree, one after another. Does this code actually do that? There are a few cases:

1. When the tree is null, you do need to create a new tree with some element, but your first case creates a tree with the whole list as its element, and returns this. This is why you get a result like ((4 1 5 13 6) () ()). You got to this base case and returned the result of (make-tree L '() '())).
2. When the first element of the list is the value of the tree, then you're right to return the tree, since you don't need to do anything else to insert that first element of the list. But then you don't do anything else with the rest of the elements. That doesn't do any good. If you had a test case like (insert-list '(2 3 4) '(2 () ())), you'd see that the return value would be (2 () ()).
3. (and 4.) In these cases you make a recursive call like (insert-list (car L) (left T)), but this doesn't make sense, because the first argument to insert-list is supposed to be a list of elements, and you're calling it with (car L) which is a single element. You're right, though, in recognizing that (car L) needs to be inserted into the left subtree of the tree, and you're constructing it correctly, if only you were calling (insert-element (car L) (left T)), instead. However, you're still not doing anything with the rest of the elements afterward.

Folds to the rescue!

If you're trying to take a list of numbers and insert the first one into a tree to get a new tree, then insert the second number into that tree, and so on, you're looking for something like this pseudo-code:

tree = initial-tree
for element in list 
  tree = insert(element,tree)
return tree

This kind of operation is typically represented functionally by a fold. I've described folds in some detail in an answer to Flattening a List of Lists, and there's lots of information about them out there. The idea is that you want to turn something like

(insert-list '(4 1 5 13 6) '())

into

(tree-insert (tree-insert (tree-insert (tree-insert (tree-insert '() 4) 1) 5) 13) 6)

and that's a left-associative fold. Let's use this definition of foldl:

(define (foldl fn init list)
  (if (null? list)
      init
      (foldl fn (fn init (car list)) (cdr list))))

In this particular case, you'd need to implement your normal tree-insert function that takes a tree and an element a returns a new tree, and then your function to insert all the elements from a list is simply

(lambda (tree elements)
  (foldl tree-insert tree elements))

For instance,

> (foldl tree-insert '() '(3 5 8 1 9))
(3 (1 () ()) (5 () (8 () (9 () ()))))
> (foldl tree-insert '() '(5 8 2 3 1 6 9))
(5 (2 (1 () ()) (3 () ())) (8 (6 () ()) (9 () ())))
> (foldl tree-insert '() '(4 1 5 13 6))             ; the test from the question
(4 (1 () ()) (5 () (13 (6 () ()) ())))