(defun min-nodes (h)
  (cond
   ((= h -1) 0)
   ((= h  0) 1)
   (t (+ 1 (min-nodes (- h 1)) (min-nodes (- h 2))))
   )
  )

(defun max-height (n)
  (max-height-aux -1 0 1 n)
  )

(defun max-height-aux (h fh fh1 n)
  (if (< n fh1)
      h
    (max-height-aux (1+ h) fh1 (+ 1 fh fh1) n)
    )
  )

;;; hbal-tree-nodes(n): list version
;;; returns a list with all completely balanced binary trees with a
;;; given number of nodes.
;;;
;;; Brute-force approach, using an auxiliary procedure which computes
;;; a list of all such trees with a given height.
;;;
;;; Note: it is possible to improve the performance using
;;; dynamic programming.  See function hbal-tree-nodes-dp

(load "p59.lisp")

(defun hbal-tree-nodes (n)
  (hbal-tree-nodes-dp n)
  )

(defun hbal-tree-nodes-bf (n)
  (let ((result nil))
    (dotimes (h (1+ (max-height n)) result)
      (setf result (append (hbal-tree-aux n h) result))
      )
    )
  )

(defun hbal-tree-aux (n h)
  (if (= n 0)
      (if (= h -1) '(()) '())
    (let ((a nil))
      (dotimes (i n a)
	(setf a (append (cart-process (hbal-tree-aux i         (- h 2))
				      (hbal-tree-aux (- n i 1) (- h 1))
				      )
			(cart-process (hbal-tree-aux i         (- h 1))
				      (hbal-tree-aux (- n i 1) (- h 1))
				      )
			(cart-process (hbal-tree-aux i         (- h 1))
				      (hbal-tree-aux (- n i 1) (- h 2))
				      )
			a))
	)
      )
    )
  )

;;; Faster, dynamic programming implementation

(defun hbal-tree-nodes-dp (n)
  (let ((a (hbal-table n (max-height n)))
	(result nil))
    (dotimes (h (1+ (max-height n)) result)
      (setf result (append (list-of-hbal-trees n h a) result))
      )
    )
  )

(defun hbal-table (n h)
  (let ((a (make-array (list (1+ n) (1+ h)) :initial-element nil)))
    (dotimes (ni (1+ n) a)
      (dotimes (hi (1+ h))
	(let ((b nil))
	  (dotimes (i ni b)
	    (setf b (append
		     (cart-process (list-of-hbal-trees i          (- hi 2) a)
				   (list-of-hbal-trees (- ni i 1) (- hi 1) a)
				   )
		     (cart-process (list-of-hbal-trees i          (- hi 1) a)
				   (list-of-hbal-trees (- ni i 1) (- hi 1) a)
				   )
		     (cart-process (list-of-hbal-trees i          (- hi 1) a)
				   (list-of-hbal-trees (- ni i 1) (- hi 2) a)
				   )
		     b))
	    )
	  (setf (aref a ni hi) b)
	  )
	)
      )
    )
  )
	  
(defun list-of-hbal-trees (n h a)
  (cond
   ((= h -2) nil)
   ((= h -1) (if (= n 0) '(()) nil))
   (t (aref a n h))
   )
  )

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

(defun hbal-tree-nodes-print (n)
  (dolist (tree (hbal-tree n))
    (print tree)
    )
  )