Search code examples
lispcommon-lispclisp

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

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

Solution

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