#-(and) "

P62B (*) Collect the nodes at a given level in a list

    A node of a binary tree is at level N if the path from the root to
    the node has length N-1. The root node is at level 1. Write a
    predicate atlevel/3 to collect all nodes at a given level in a
    list.

    % atlevel(T,L,S) :- S is the list of nodes of the binary tree T at level L

    Using atlevel/3 it is easy to construct a predicate levelorder/2
    which creates the level-order sequence of the nodes. However,
    there are more efficient ways to do that.
"

;; Simple recursive solution:

;; Notice the above definition use a 1-based index for the level.
;; As always, this is a bad choice, hence the use of (= 1 level) instead of (zerop level).
;; http://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF


(defun collect-nodes-at-level (tree level)
  (cond
    ((binary-tree-empty-p tree) '())
    ((= 1 level)             (list tree))
    (t  (append (collect-nodes-at-level (binary-tree-left  tree) (1- level))
                (collect-nodes-at-level (binary-tree-right tree) (1- level))))))

;; Note: nconc could be used instead of append, since all the lists
;;       returned by collect-nodes-at-level are newly allocated lists.


;;;; THE END ;;;;