Binary Trees in Scheme

Question

Consider the following BNF defining trees of numbers. Notice that a tree can either be a leaf, a node-1 with one subtrees, or a node-2 with two subtrees.

tree ::= (’leaf number)
| (’node-1 tree)
| (’node-2 tree tree)

a. Write a template for recursive procedures on these trees.

b. Define the procedure (leaf-count t) that returns the number of leaves in t

> (leaf-count ’(leaf 5))

1

> (leaf-count ’(node-2 (leaf 25) (leaf 17)))

2

> (leaf-count ’(node-1
(node-2 (leaf 4)
(node-2 (leaf 2) (leaf 3)))))

3

Here's what I have so far:

;define what a leaf, node-1, and node-2 is
(define leaf list)
(define node-1 list)
(define node-2 list)

;procedure to decide if a list is a leaf or a node
(define (leaf? tree) (number? (car tree)))
(define (node? tree) (pair? (car tree)))

(define (leaf-count tree)
 (cond ((null? tree) 0)
        ((number? tree) 0)
        ((leaf? tree) 1)
        (else (+ (leaf-count (car tree))
                 (leaf-count (cdr tree))))))

It looks like it should run just fine, but when I try to run it using a simple test case like

(leaf-count '(leaf 5))

I get the following error message:

car: expects argument of type pair; given leaf

What does this error message mean? I am defining a leaf as a list. But for some reason, it's not seeing that and gives me that error message.

Answer 1

Solving other people's assignments is fun, indeed.

(define leaf-count
  (match-lambda 
   [(list 'leaf x)     1]
   [(list 'node-1 t)   (leaf-count t)]
   [(list 'node-2 l r) (+ (leaf-count l) (leaf-count r))]))