(defun tree-node (val children)
  (cons val children))

(defun node-value (node)
  (car node))

(defun node-children (node)
  (cdr node))

(defun node-value-multi (nodes)
  (if (null nodes)
      '()
    (cons (node-value (car nodes))
          (node-value-multi (cdr nodes)))))

(defun node-children-multi (nodes)
  (if (null nodes)
      '()
    (append (node-children (car nodes))
            (node-children-multi (cdr nodes)))))

(defun tree-values-dfs (root)
  (cons (node-value root)
        (tree-values-dfs-multi (node-children root))))

(defun tree-values-dfs-multi (roots)
  (if (null roots)
      '()
    (append (tree-values-dfs (car roots))
            (tree-values-dfs-multi (cdr roots)))))

(defun tree-values-bfs (root)
  (tree-values-bfs-multi (list root)))

(defun tree-values-bfs-multi (roots)
  (if (null roots)
      '()
    (append (node-value-multi roots)
            (tree-values-bfs-multi (node-children-multi roots)))))

(defun binary-tree-node (val left-child right-child)
  (list val left-child right-child))

(defun left-child (node)
  (cadr node))

(defun right-child (node)
  (caddr node))

(defun bt-node-children (node)
  (remove nil (cdr node)))

(defun elementp (el tree)
  (if (null tree)
      nil
    (let ((val (node-value tree)))
      (or (= el (node-value tree))
          (and (< el val) (elementp el (left-child tree)))
          (and (> el val) (elementp el (right-child tree)))))))

(defun my-adjoin (elem tree)
  (if (null tree)
      (binary-tree-node elem nil nil)
    (let ((val (node-value tree))
          (left (left-child tree))
          (right (right-child tree)))
      (cond ((= elem val) tree)
            ((< elem val) (binary-tree-node val
                                            (my-adjoin elem left)
                                            right))
            (t (binary-tree-node val
                                 left
                                 (my-adjoin elem right)))))))