Design Pattern: Binary Tree Recursion

This pattern is like the one for lists, except that it calls itself twice for interior nodes. This is essentially the same as the divide-and-conquer design pattern.

(defun myfun (tree)
         (if (interior? tree)
                 (combine (myfun (left tree))
                         (myfun (right tree)))
                 (if (test tree) ; leaf
                         (baseanswer tree)
                         safeanswer ) ) )

(defun addnums (tree)  ; sum all numbers in tree
  (if (consp tree)
      (+ (addnums (first tree))
         (addnums (rest tree)) )
      (if (numberp tree)
          tree
          0) ) )

The safeanswer should be an identity element for the combine operation, i.e. a value that, when combined with any other value, yields the other value.