Finding the maximum number of child nodes in a tree

First, I should make it clear that this is required for an academic project. I am trying to find the maximum number of child nodes for any node in a tree, using Common Lisp.

My current code is shown below - I'm not 100% on the logic of it, but I feel it should work, however it isn't giving me the required result.

(defun breadth (list y)
  (setf l y)
        (mapcar #'(lambda (element) 
              (when (listp element) 
         (when (> (breadth element (length element)) l) 
             (setf l (breadth element (length element)))
           ))) list)

l)

(defun max-breadth(list)
  (breadth list (length list))
  )

As an example, running

(max-breadth '(a ( (b (c d)) e) (f g (h i) j)))

should return 4.

Edit: Trace results and actual return values, forgot these:

CG-USER(13): (max-breadth '(a ( (b (c d)) e) (f g (h i) j)))
 0[6]: (BREADTH (A ((B (C D)) E) (F G (H I) J)) 3)
   1[6]: (BREADTH ((B (C D)) E) 2)
     2[6]: (BREADTH (B (C D)) 2)
       3[6]: (BREADTH (C D) 2)
       3[6]: returned 2
     2[6]: returned 2
   1[6]: returned 2
   1[6]: (BREADTH (F G (H I) J) 4)
     2[6]: (BREADTH (H I) 2)
     2[6]: returned 2
   1[6]: returned 2
 0[6]: returned 2
2

Does anyone have any ideas where I'm going wrong?开发者_开发百科 I suspect it's related to the second conditional, but I'm not sure.

---

First, standard formatting:

(defun breadth (list y)
  (setf l y)
  (mapcar #'(lambda (element) 
              (when (listp element) 
                (when (> (breadth element (length element)) l) 
                  (setf l (breadth element (length element))))))
          list)
  l)

(defun max-breadth (list)
  (breadth list (length list)))

Your problem is the (setf l y), which should give you a warning about l being undefined. Setf should not be used on unbound variables. Use let to make a lexical scope:

(defun breadth (list y)
  (let ((l y))
    (mapcar #'(lambda (element) 
                (when (listp element) 
                  (when (> (breadth element (length element)) l) 
                    (setf l (breadth element (length element))))))
            list)
    l))

Then, instead of two nested when, use a single one and and:

              (when (and (listp element)
                         (> (breadth element (length element)) 1))
                (setf l (breadth element (length element))))

I find dolist more concise here:

  (dolist (element list)
    (when (and (listp element)
               (> (breadth element (length element)) l))
      (setf l (breadth element (length element)))))

The parameter y is always the length of the parameter list, so this call can be simplified. You also do not need to alias y:

(defun breadth (list &aux (y (length list)))
  (dolist (element list)
    (when (and (listp element)
               (> (breadth element) y))
      (setf y (breadth element))))
  y)

You could eliminate the double recursive call through a let, but we can use max here:

(defun breadth (list &aux (y (length list)))
  (dolist (element list)
    (when (listp element)
      (setf y (max y (breadth element)))))
  y)

You could also use reduce for this:

(defun breadth (l)
  (if (listp l)
      (reduce #'max l
              :key #'breadth
              :initial-value (length l))
      0))

---

L is not a local variable, so the function will return the last value assigned to it (ie, the breadth of the last subtree).

Use LET to declare a local variable:

(LET ((l y))
    ...
)

---

Isn't the correct answer 6? Since e and j in your example are also technically child nodes? If that's how you're defining your problem, the following solution should get you there:

(defun max-breadth (lst)
  (cond
    ((atom lst) 0)
    ((every #'atom lst) (length lst))
    (t (+ (max-breadth (car lst)) (max-breadth (cdr lst))))))

version 2:

(defun max-breadth (lst)
  (cond
    ((atom lst) 0)
    ((every #'atom lst) (length lst))
    (t (+ 
         (max-breadth (car lst))
         (max-breadth (remove-if-not #'consp (cdr lst)))))))