Check if n-ary tree is balanced in Common Lisp

I'm trying to write the code to check whether an n-ary tree is balanced or not in clisp. The tree is given like this:

(A (B (E (I))(F))(C (G))(D))

which would look like:

      A
   /  |  \
  B   C   D
 /\   |   
E  F  G   
|
I

Which would be unbalanced.

I was thinking about solving it using something like:

the max level of all leaves of a letter - the min level of all leaves shouldnt be bigger than 1.
I thought about applying this rule for A,B,C first. If the difference is not bigger than 1, then check for E,F,G until I either checked all the possible letters and the tree is balanced or I got a difference bigger than 1 which means it's unbalanced.

This is the code for the min/max level:

(defun nrlvlmax (tail) 
(cond 
    ( (null tail) 0)
    ( (listp (car tail)) (max ( + 1 (nrlvl (car tail))) (nrlvl (cdr tail))))
    ( t (nrlvl (cdr tail)))
)

)

I don't know how to parse the list and apply my rule. I shouldn't be using map/lamba functions, only like basics. How to parse the given list?

Solution

Here is a possible solution that does not use higher order functions.

The idea is to calculate the maximum level of a tree and its minimun level, and check their difference.

To calculate the maximum (or minimun) level of a tree we use two mutually recursive functions: the first calculates the maximun (minimun) level of tree, the second calculates the maximum (minimun) of all its children.

Of course, if a tree has children, then its level is 1 plus the maximum (minimun) level of its children.

The function for the children has two parameters, the first one is the rest of the children to be considered, the second one is the current value of the maximum (minimum).

(defun maxlevel(tree)
  (cond ((null tree) 0)
        ((null (cdr tree)) 1)
        (t (1+ (max-for-children (cddr tree) (maxlevel (cadr tree)))))))

(defun max-for-children(children current-max)
  (if (null children)
      current-max
      (max-for-children (cdr children) (max current-max (maxlevel (car children))))))

(defun minlevel(tree)
  (cond ((null tree) 0)
        ((null (cdr tree)) 1)
        (t (1+ (min-for-children (cddr tree) (minlevel (cadr tree)))))))

(defun min-for-children(children current-min)
  (if (null children)
      current-min
      (min-for-children (cdr children) (min current-min (minlevel (car children))))))

(defun balanced(tree)
  (= (maxlevel tree) (minlevel tree)))

This is for perfectly balanced trees. If you allow trees with difference of at most one between the levels of the tree, then substitute the last function with:

(defun balanced(tree)
  (<= (abs (- (maxlevel tree) (minlevel tree))) 1))