```#-(and) "

P61 (*) Count the leaves of a binary tree
A leaf is a node with no successors. Write a predicate count-leaves/2 to count them.

% count-leaves(T,N) :- the binary tree T has N leaves

"

(defun binary-tree-leaf-p (node)
(and (binary-tree-p node)
(binary-tree-empty-p (binary-tree-left  node))
(binary-tree-empty-p (binary-tree-right node))))

;; Simple recursive solution:

(defun count-leaves (tree)
(cond
((binary-tree-empty-p tree)  0)
((binary-tree-leaf-p  tree)  1)
(t (+ (count-leaves (binary-tree-left  tree))
(count-leaves (binary-tree-right tree))))))

;; For very deep trees, here is a solution avoiding stack use:

(defun count-leaves (tree)
(if (binary-tree-empty-p tree)
0
(loop
:with stack = (list tree)
:for node = (pop stack) :then (if (binary-tree-empty-p (binary-tree-left node))
(pop stack)
(binary-tree-left node))
:while node
:unless (binary-tree-empty-p (binary-tree-right node))
:do (push (binary-tree-right node) stack)
:when (binary-tree-leaf-p node) :count 1)))

;;;; THE END ;;;;```
ViewGit