Check if n-ary tree is balanced in Common Lisp

Question

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?

Answer 1

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

Answer 2

My previous solution is not efficient for two reasons:

1. the tree is visited twice,
2. the algorithm does not stop as soon as it finds a path from the root to a leaf that violates the balancing condition.

So, here is a more efficient solution, that visit the tree only once, and stops as soon as it finds a path too short or too long.

The basic ideas are:

1. all the work is performed by a inner function min-max that returns a couple of values: minimun depth and maximum depth of subtrees rooted at the current argument of the function, this allows visiting the tree only once;

2. at each recursive call the function receives the current level, the current minimum level and the current maximum level, so that it can check as soon as possible if the tree is unbalanced and the visit must be stopped immediately. For the first child of a node, the current maximum and minimum are set to nil (and for this reason I defined two auxiliary functions that calculates the minimum or maximum even if the second argument is nil).

Note that the main function returns either nil, if the tree is unbalanced, or the minimun depth of the tree.

(defun mymin(x y)
  (if y (min x y) x))

(defun mymax(x y)
  (if y (max x y) x))

(defun balanced(tree)
  (labels ((min-max(tree current-level current-min current-max)
             (when (and current-min (> (1- current-level) current-min))
                (return-from balanced nil))                  ; this path is too long
             (if (null (cdr tree))                           ; if it is a leaf node
                 (if (and current-max (< (1+ current-level) current-max))
                     (return-from balanced nil)              ; this path is too short
                     (values current-level current-level))   ; return normally
                 (loop for child in (cdr tree)               ; find min-max for each child
                    do (multiple-value-bind (min1 max1)
                           (min-max child (1+ current-level) current-min current-max)
                         (setf current-min (mymin min1 current-min)
                               current-max (mymax max1 current-max)))
                    finally (return (values current-min current-max))))))
    (values (min-max tree 0 nil nil))))

Finally, note that the function uses a loop. A recursive version could be produced, but this would only complicate the solution and makes it unnatural.