;;; hbal-tree(n): list version
;;; returns a list with all completely balanced binary trees with a
;;; given height.
;;;

(defun hbal-tree (h)
  (cond
   ((<= h -2) ())
   ((= h -1) '(()) )
   (t (append (cart-process (hbal-tree (- h 2))
			    (hbal-tree (- h 1))
			    )
	      (cart-process (hbal-tree (- h 1))
			    (hbal-tree (- h 1))
			    )
	      (cart-process (hbal-tree (- h 1))
			    (hbal-tree (- h 2))
			    )
	      ))
   )
  )

(defun cart-process (l1 l2)
  (process (cart-product l1 l2))
  )

(defun process (lista)
  (mapcar #'(lambda (x) (cons 'x x)) lista)
  )

(defun cart-product (l1 l2)
  (let ((a nil))
    (dolist (t1 l1 a)
      (setf a (append (mapcar #'(lambda (x) (list t1 x)) l2) a))
      )
    )
  )

;;; hbal-tree: print version
;;; call list version and then print each element

(defun hbal-tree-print (h)
  (dolist (tree (hbal-tree h))
    (print tree)
    )
  )