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))]))

Answer 2

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? (cadr tree)))
(define (node? tree) (pair? (cadr tree)))

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

I got it to work with a minor adjustment: change the conditionals to check the cadr of the list as that is what contains the info. The car of the list in this case is just the label of what the data is (leaf, node, etc.). Not quite. I got it to work for the most basic of test cases, but not for more complex ones like

(leaf-count '(node-2 (leaf 25) (leaf 17)))

Answer 3

You've quoted leaf, (leaf-count '(leaf 5)) so it's a symbol, not a variable you've defined earlier. That's the cause of the error, but not the thing you should fix. Your three defines have no much sense and your procedures to detect leaf or node do not match the BNF specification.

Here is a tree from your own example: ’(node-1 (node-2 (leaf 4) (node-2 (leaf 2) (leaf 3)))). It's quoted so node-1, node-2 and leaf are just symbols and need not to be defined. Now write leaf? and node? functions that could detect what the various elements of above tree are. Here is a test case for you where all the function calls should return true:

(define a-tree ’(node-1 (node-2 (leaf 4) (node-2 (leaf 2) (leaf 3)))))
(node? a-tree)
(node? (car (cdr a-tree)))
(leaf? (car (cdr (car (cdr a-tree)))))
(node? (car (cdr (cdr (car (cdr a-tree))))))
(leaf? (car (cdr (car (cdr (cdr (car (cdr a-tree))))))))

Once this works, counting should be no problem either (altough your current method wouldn't work, I propose writing left-subtree and right-subtree functions to help you with that).