;; figure 4.5
(defstruct (tnd (:print-function
					(lambda (n s d)
						(format s "<~A>" (tnd-elt n)))))
	elt (l nil) (r nil))
	
(defun bst-insert (obj bst <)
	(if (null bst)
		(make-tnd :elt obj)
		(let ((elt (tnd-elt bst)))
			(if (eql obj elt)
				bst
				(if (funcall < obj elt)
					(make-tnd
						:elt elt
						:l (bst-insert obj (tnd-l bst) <)
						:r (tnd-r bst))
					(make-tnd
						:elt elt
						:r (bst-insert obj (tnd-l bst) <)
						:l (tnd-l bst)))))))

(defun bst-find (obj bst <)
	(if (null bst)
		nil
		(let ((elt (tnd-elt bst)))
			(if (eql obj elt)
				bst
				(if (funcall < obj elt)
					(bst-find obj (tnd-l bst) <)
					(bst-find obj (tnd-r bst) <))))))
					
(defun bst-min (bst)
	(and bst
		(or (bst-min (tnd-l bst)) bst)))
		
(defun bst-max (bst)
	(and bst
		(or (bst-max (tnd-r bst)) bst)))

(defun init-bst ()
	(let ((nums nil))
	(dolist (x '(5 8 4 2 1 9 6 7 3))
			(setf nums (bst-insert x nums #'<))) nums))