#-(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
"
(load "p54a")
(load "p55")
(load "p56")
(load "p57")
(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 ;;;;