Lisp program to check whether a binary tree is a Binary Search Tree

You can express your definitions in code to make your life easier.

A node is represented as a list of three things: a key, a left subtree, and a right subtree.

(defun node-key (node)
  (first node))

(defun node-left-subtree (node)
  (second node))

(defun node-right-subtree (node)
  (third node))

For a tree to be a binary search tree, four conditions must be met, unless both subtrees are empty:

• the left subtree must be a binary search tree
• the right subtree must be a binary search tree
• the largest key of the left subtree (if present) must be smaller than the root key
• the smallest key of the right subtree (if present) must be bigger than the root key

Note: the naming convention in Lisp is to write everything in lower case, with word parts separated by dashes. A predicate, i. e. a function that is used to obtain a truth value, ends with p. The predicate for a binary search tree might be named bst-p or binary-search-tree-p. The function to obtain the largest key of a bst might be called bst-largest-key.

In order to get the largest (smallest) key of a BST, you only need to recurse on the right (left) subtree.

Here's a scheme procedure that might help you.

(define (is-bst l)
  (define (loop node proc)
    (if (null? node)
        #t
        (and (proc (car node))
             (loop (cadr node)
                   (curry > (car node)))
             (loop (caddr node)
                   (curry < (car node))))))
  (loop l (const #t)))

It can be frustrating to fix a program when your input data is the source of the bugs. I had to fix your (()) and (13). Use multiple lines and the auto-indenter to easily find mistakes.

(is-bst '(8 (3 (1 () ())
               (6 (4 () ())
                  (7 () ())))
            (10 ()
                (14 (13 () ())
                    ()))))

;; #t

Invalidate one of the nodes to ensure is-bst detects a non-bst.

(is-bst '(8 (3 (1 () ())
               (6 (4 () ())
                  (7 () ())))
            (10 ()
                (2 (13 () ()) ;; 14 changed to 2; invalid tree
                   ()))))

;; #f

To make a slight improvement, notice we called (car node) three times in the procedure above. This should be avoided with the use of let.

(define (is-bst l)
  (define (loop node proc)
    (if (null? node)
        #t
        (let ((value (car node)))
          (and (proc value)
               (loop (cadr node)
                     (curry > value))
               (loop (caddr node)
                     (curry < value))))))
  (loop l (const #t)))

Another interesting way is using streams, which can be easily implemented using basic procedures. We could write a generic traverse procedure to traverse our trees.

(define (traverse bst)
  (if (null? bst)
      empty-stream
      (stream-append (traverse (cadr bst))
                     (stream (car bst))
                     (traverse (caddr bst)))))

(define tree
  '(8 (3 (1 () ())
               (6 (4 () ())
                  (7 () ())))
            (10 ()
                (14 (13 () ())
                    ()))))

(stream->list (traverse tree))
;; '(1 3 4 6 7 8 10 13 14)

Now we write is-bst to simply check that the values come out in ascending order.

(define (is-bst l)
  (define (loop x s)
    (if (stream-empty? s)
        #t
        (let ((y (stream-first s)))
          (and (< x y)
               (loop y (stream-rest s))))))
  (loop -inf.0
        (traverse l)))


(is-bst tree)
; #t

(is-bst '(1 (2 () ())
            (3 () ())))
; #f

Because a stream is used, the values come out lazily. If an early #f is found, iteration of the stream is stopped and the computation is finished.