Binary Tree Recursion

While recursion is not always the best method for linked lists, it usually is the best method for trees. We don't have a problem with stack depth because depth is only O(log(n)) if the tree is balanced.

Suppose that we want to add up all the numbers, or collect a set of symbols, in a Lisp tree.

(defn addnums [tree]
  (if (cons? tree)          ; interior node
      (+ (addnums (first tree))
         (addnums (rest tree)) )
      (if (number? tree)         ; leaf node
          tree
          0) ) )   ; safe: identity value

(defn symbolset [tree]
  (if (cons? tree)          ; interior node
      (union (symbolset (first tree))
             (symbolset (rest tree)) )
      (if (symbol? tree)
          (list tree)
          '()) ) )