How to create a function that returns the number of nodes in a tree on a given level

Question

I tried this but it doesn't work. As constraints, I can't use predefined functions, only cond, eql and mapcar . I can't use also ifs or variables or loops

(defun countNodes (level tree)
  (cond
    ((null tree) 0)
    ((eql level 0) 1)
    (t (apply #'+ (mapcar (lambda (level subtree) (countNodes (1- level) subtree)) tree)))
)
)

(write (count-nodes-on-level '(1 (2 (3 (6 7) 4) 5)) 4))

This is the given error: *** - MAPCAR: A proper list must not end with1

I tried to look on stackoverflow for some answer but I didn't find anything that could help me

EDIT (write (count-nodes '(a (b (c)) (d) (e (f))) 1)) will return 1

this is an example that i found and sorry for my mistake but I got wrong the definition of the supposed tree.It looks like the root is 'a' and it has 3 child, 'b' 'd' and 'e', 'c' is child of 'b' and 'f' is child of e

Answer 1

Given your example, without a precise definition of tree, I suppose that a tree is either an atom (meaning that it is a tree with root the atom, and without children), or a list, possibly empty, of which the car is the root, and the cdr is the list of the children.

With this hypothesis, here is a version of the function that can solve your problem:

(defun countNodes (level tree)
  (cond ((null tree) 0)
        ((eql level 0) 1)
        ((atom tree) 0)
        (t (apply #'+ (mapcar 
                       (lambda (subtree) (countNodes (1- level) subtree))
                       (cdr tree))))))

Answer 2

I would adopt the following requirements and write it like this:

(defun count-nodes (tree level)
  (cond
    ((atom tree) 0)
    ((plusp level) (reduce #'+ (mapcar (lambda (subtree)
                                         (count-nodes subtree (1- level)))
                                        tree)))
    (t (length tree))))

Note that we never return 1 for the atom case; for both the empty subtree and an atom like 42, we just return 0. This works because length counts the atoms for us already; if we return 1, we get a double count.

Some tests:

[1]> (count-nodes '(1 2 3 (4)) 0)
4
[2]> (count-nodes '(1 2 3 (4)) 1)
1
[3]> (count-nodes '(1 2 3 (4)) 2)
0
[4]> (count-nodes '(1 2 3 (4)) 3)
0

As you can see, at level 0 we just return the length, which is 4. At level 1, the length of (4) gets reported. Then after that zero.

[5]> (count-nodes '(1 2 3 (4) (5) (6 7 8)) 1)
5

Here, the lengths of (4) (5) and (6 7 8) get added together, yielding 5.

If reduce and length are not on the list of allowed functions, you can write them yourself. length can be made out of mapcar along these lines:

(defun len (list)
  (let ((count 0))
    (mapcar (lambda (item) (inc count)) list)
    count))

EDIT: Now, it turns out that the definition of "tree" for the purposes of the problem is a labeled abstraction. That is to say, the list (1 2 3) is being given a meaning that the first element is a label, and only the se cond and subsequent elements are the children. A label is not a subtree and thus not recursed into or counted. The quick fix to make the code ignore labels is this:

(defun count-nodes (tree level)
  (cond
    ((atom tree) 0)
    ((plusp level) (reduce #'+ (mapcar (lambda (subtree)
                                         (count-nodes subtree (1- level)))
                                        (cdr tree)))) ;; cdr here
    (t (length (cdr tree))))) ;; cdr here

Examples:

[2]> (count-nodes '(a b c) 0)
2
[3]> (count-nodes '(a b c) 1)
0
[4]> (count-nodes '(a (b) c) 1)
0
[5]> (count-nodes '(a (b 1) c) 1)
1
[6]> (count-nodes '(a (b 1) (c 1)) 1)
2
[7]> (count-nodes '(a (b 1) (c 1 (d 2 3))) 1)
3
[8]> (count-nodes '(a (b 1) (c 1 (d 2 3))) 2)
2

We now need to answer the requirements question: is ()/nil actually a valid tree? Is (a 1 ()) a valid tree node with label a and two children 1 and nil, or is () an invalid node lacking a label? With the quick fix to the code above, we take the former view: () is just another atom. We tolerate it silently and count it.