Jotter <2026-03-23 Mon>

(defstruct node
  (value  nil :type fixnum)
  (left   nil :type bt)
  (right  nil :type bt))

(deftype bt () '(or node null))

(make-node :value 3)

(node-value (make-node :value 3))

(make-node :left (make-node :value 2)
           :value 3
           :right (make-node :value 4))

(node-left (make-node :left (make-node :value 2)
                      :value 3
                      :right (make-node :value 4)))

(node-value (node-left (make-node :left (make-node :value 2)
                                  :value 3
                                  :right (make-node :value 4))))

(node-p (make-node :left (make-node :value 2)
                   :value 3
                   :right (make-node :value 4)))

;;;;

(defun test-sum-bt ()
  (and (= 3 (sum-bt (make-node :value 3)))
       (= 2 (sum-bt (make-node :value 2)))
       (= 8 (sum-bt (make-node :value 2
                               :left (make-node :value 2)
                               :right (make-node :value 4))))
       (= 0 (sum-bt nil))
       (= 0 (sum-bt (make-node :value 0)))
       (= 9 (sum-bt (make-node :left (make-node :value 2)
                               :value 3
                               :right (make-node :value 4))))))

(defun sum-bt (bt)
  "Sum all the numbers in the binary tree, BT"
  (cond ((null bt) 0)
        (t (+ (node-value bt)
              (sum-bt (node-left bt))
              (sum-bt (node-right bt))))))

;;;;

(defun test-mth ()
  (and (equal :error (mth 0 ()))
       (equal 1 (mth 1 '(0 1 2 3)))
       (equal :error (mth 3 '(0 1 2)))
       (equal 99 (mth 0 '(99)))
       (equal :error (mth 1 ()))))

(defun mth (m ns)
  "Return the MTH element of the list of integers, NS, where the indexing is
zero based."
  (cond ((null ns) :error)
        ((zerop m) (first ns))
        (t (mth (- m 1) (rest ns)))))

(test-mth)