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.

Go to the first, previous, next, last section, table of contents.