Question

(define (count-leaves t)
(cond ((null? t) 0)
((not (pair? t)) 1)
(else (+ (count-leaves (car t))
(count-leaves (cdr t))))))

Trace this function with the example:

For example, (count-leaves '((4 5 6) (1 2) () (3) )) returns 6

Answer 1

Here is the trace of the function for the given example:

At the top level, count-leaves is called on  '((4 5 6) (1 2) () (3)) which is the list [[4,5,6], [1,2], [], [3]]

Since the given list is a pair (as it contains 4 elements not 2), and is not even null, we move to the else condition.

We have car t = [4,5,6] and cdr t = [[1,2], [], [3]]

Now count-leaves is called on (car t) which does the following:

Again [4,5,6] have more than 2 elements, we call count-leaves 4 which returns 1 (as 4 is not a pair) and count-leaves (5,6) returns 2 as all these are leaves. Hence finally we return 3 from here.

Similarly the function is called on cdr t = [[1,2], [], [3]],

This calls thee functions:

count-leaves [1,2] -> 2

count-leaves [] -> 0

count-leaves [3] -> 1

Hence this part also returns 3 (the sum of above calls)

Finally we return the sum of both the above calls = 3 + 3 = 6.

Hence 6 is returned.

You can comment below the answer in case of any doubts and I will be happy to help.

Please give a thumbs up if the answer could be of help!

All the best!