#-(and) "

Binary Trees

A binary tree is either empty or it is composed of a root element and
two successors, which are binary trees themselves.  [p67]   

In Lisp we represent the empty tree by 'nil' and the non-empty tree by
the list (X L R), where X denotes the root node and L and R denote the
left and right subtree, respectively. The example tree depicted
opposite is therefore represented by the following list:

(a (b (d nil nil) (e nil nil)) (c nil (f (g nil nil) nil)))

Other examples are a binary tree that consists of a root node only:

(a nil nil) or an empty binary tree: nil.

You can check your predicates using these example trees. They are given as test cases in p54.lisp.

P54A (*) Check whether a given term represents a binary tree
    Write a predicate istree which returns true if and only if its argument is a list representing a binary tree.
    Example:
    * (istree (a (b nil nil) nil))
    T
    * (istree (a (b nil nil)))
    NIL
"

;; Notice that  there are a lot of ways to represent trees.
;; Therefore it important to use a functional abstraction, to avoid
;; writing code dependant on a specific representation.
;;
;; Also, in the following problems, references to prolog terms are not
;; translated to lisp, and terms for trees are given as:
;; 
;;     T = t(x, t(x, nil, nil), t(x, nil, t(x, nil, nil))) 
;; 
;; We could translate this as having the symbol BINARY-TREE prefixing the
;; lists representing tree nodes:
;; 
;;     (BINARY-TREE a (BINARY-TREE b nil nil) (BINARY-TREE c nil (BINARY-TREE f nil)))
;; 
;; This can be trivially implemented by adding the :NAMED option to defstruct, in which
;; case an implementation of BINARY-TREE-P is provided by destruct.


(defstruct (binary-tree (:type list) :named)
  label left right)
;; This defstruct defines the following functional abstraction:
;; (make-binary-tree :label label :left left :right right)
;; (binary-tree-label node)
;; (binary-tree-left  node)
;; (binary-tree-right node)
;; (copy-binary-tree node) ; shallow copy.
;; We add:
(defun make-empty-binary-tree () 'nil)
(defun binary-tree-empty-p (node) (null node))
(defun binary-tree-p    (node)
  (or (binary-tree-empty-p node)
      (let ((nodes '()))
        (labels ((check-node (node)
                   (and (listp node)
                        (not (member node nodes)) ; check circular structures.
                        (progn (push node nodes) t)
                        (eql 3 (list-length node))
                        (or (null (second node)) (check-node (second node)))
                        (or (null (third  node)) (check-node (third  node))))))
          (check-node node)))))
;; We add:
(defun binary-tree-from-sexp (sexp) sexp)
;; it would be good form to use it, so that if we change the
;; implementation of the above functional abstraction, we can still
;; use the tree sexps defined by for these problems:
;; (binary-tree-p (binary-tree-from-sexp '(a (b (d nil nil) (e nil nil)) (c nil nil))))


(defun binary-tree-height (tree)
  (if (binary-tree-empty-p tree)
      0
      (+ 1 (max (binary-tree-height (binary-tree-left tree))
                (binary-tree-height (binary-tree-right tree))))))




(defparameter *tree-0* 'nil)
(defparameter *tree-1* '(a nil nil))
(defparameter *tree-2* '(a (b (d nil nil) (e nil nil)) (c nil (f (g nil nil) nil))))


;; Solution:

(defun istree (object)
  (binary-tree-p object))


(assert (equal (mapcar (function istree)
                       (list *tree-0* *tree-1* *tree-2*
                             '(a b c)
                             '(a (nil 1 2) (nil 3 4) d)
                             '(a (nil nil nil) (nil nil nil) d)))
               '(T T T NIL NIL NIL)))

;;;; THE END ;;;;