Using Type Predicates

We can easily write a procedure pair-tree-sum to give us the sum of a binary tree of integers, whose interior nodes are pairs and whose leaves are the integers.

Our notion of a "pair tree" is a binary tree of pairs. Here we're doing something a little strange, because in general we're making improper lists. We'll regard the car and cdr fields of a pair as the "left child" and "right child" fields of a tree node. A proper list wouldn't be a pair tree, because it the last pair in the list would point to the empty list object, not a number.

(Later, I'll show a record facility that allows us to build "tree node" records that are not pairs. That's nicer, because it doesn't confuse pairs' roles in improper lists with their roles in trees. For now, we'll stick with pairs, because the point of this example is recursion, not the details of records.)

Just as we did for proper lists, we start by characterizing this data structure recursively. We'll consider any subtree of a pair-tree to be a pair-tree. This includes the leaves, e.g., the numbers in a tree of numbers. (This is analogous to the way we considered the empty list to be a kind of list in the recursive characterization of lists.)

A pair tree is either

• a leaf (not a pair), or
• a pair, whose car and cdr values are pair-trees.

Our recursive summing procedure will have to deal with these two cases:

• a numbers, i.e., leaves of a tree of numbers, and
• pairs, in which case it should sum the left and right subtrees, and add those sums together.

The first case is the base case for the recursion. The sum of a leaf is the numeric of that leaf.

The second case is the recursive case, where we have a subtree to sum.

Scheme>(define (pair-tree-sum pair-tree)
          (cond ((not (pair? pair-tree)) ;; if leaf
                 pair-tree)              ;; return it
                (else                    ;; else add sums of subtrees
                 (+ (pair-tree-sum (car pair-tree))
                    (pair-tree-sum (cdr pair-tree))))))

Try this out, and make sure you understand why it works.

Scheme>(pair-tree-sum 1)
1
Scheme>(pair-tree-sum '(1 . 2))
3
Scheme>(pair-tree-sum '((40 . 30) . (20 . 10)))
100

Notice how simple pair-tree-sum is, and how it depends on getting the base case for the recursion right. If we hadn't considered the leaves to be pair-trees in their own right, it would have gotten much uglier. For example, if we'd "bottomed out" at pairs whose left and right children weren't both pairs, we'd have had more cases to deal with--cases where one child is a leaf but the other's not.

Add display and newline expressions at the beginning of pair-tree-sum, as we did for list-sum, and try it out again. Be sure you understand the output in terms of the recursive call pattern.