tree.el

;; Binary tree

(cl-defstruct tree
  (left nil)
  (right nil)
  (value nil)
  (comparator #'<))

(cl-defun tree-insert (tree val &optional (comparator #'<))
    (cond
     ((eq nil tree)
      (setf tree (make-tree :value val
                            :comparator comparator)))
     ((eq nil (tree-value tree))
      (setf (tree-value tree) val))
     ((funcall (tree-comparator tree)
               val
               (tree-value tree)) ; val is smaller than tree-val
             (if (tree-left tree)
                 (tree-insert (tree-left tree)
                              val
                              (tree-comparator tree))
               (setf (tree-left tree) (make-tree :value val
                                                 :comparator (tree-comparator tree)))))
     (t ; val is not smaller than tree-val
      (if (tree-right tree)
          (tree-insert (tree-right tree)
                       val
                       (tree-comparator tree))
        (setf (tree-right tree) (make-tree :value val
                                           :comparator (tree-comparator tree))))))
  tree)

(defun leaf? (tree)
  (and (null (tree-left tree))
       (null (tree-right tree))))

(defun tree-find (tree val)
  (when tree
    (let ((comparator (tree-comparator tree))
          (tree-val (tree-value tree)))
      (cond
       ((equal tree-val val) tree)
       ((funcall comparator val tree-val) (tree-find (tree-left tree) val))
       (t (tree-find (tree-right tree) val))))))