99 Clojure Problems – 61: Count the Leaves of a Binary Tree.

"A leaf is a node with no successors. Write a method leaf-count to count them."

(deftest p61-count-leaves
  (is  (= (leaf-count '[x [x [x nil nil] nil] [x nil nil]]) 2)))

I simply walked the tree and counted all the leaves. Both functions, for detecting leaves and walking the tree, existed from previous exercises. See the solution on Github.

Read more about this series.

99 Clojure Problems – 60 (alternative solution): Construct Height-balanced Binary Trees with a Given Number of Nodes.

This post describes an alternative solution to problem 60 based on logic programming. Check out my previous post for a functional Clojure solution.

The original 99 problems were compiled to teach Prolog. Clojure's core.logic implements a minimal logic DSL called miniKanren using Clojure as the host language. In this post I reimplement the solution to problem 60 based on core.logic. If you want to learn more about miniKanren 'The Reasoned Schemer' and minikanren.org are probably good places to start.

My solution is not fully relational, I rely on the groundness of certain terms. See the comments below. Full source can be found on Github.

"Construct height-balanced binary trees with a given number of nodes. Consider a height-balanced binary tree of height H. What is the maximum number of nodes it can contain? Clearly, MaxN = 2H - 1.

However, what is the minimum number MinN? This question is more difficult. Try to find a recursive statement and turn it into a function min-hbal-nodes that takes a height and returns MinN."

(defne min-nodes [h n]
  ([0 0])
  ([1 1])
  ([h n]
   (fd/> h 1)
   (fresh [h1 h2 n1 n2]
     (is h1 h dec)
     (is h2 h1 dec)
     (min-nodes h1 n1)
     (min-nodes h2 n2)
     (fd/in n1 n2 n (fd/interval 0 Integer/MAX_VALUE))
     (fd/eq (= (+ 1 n1 n2) n)))))

(defn min-hbal-nodes  
  [h]
  (run 1 [q]
    (min-nodes h q)))

"On the other hand, we might ask: what is the maximum height H a height-balanced binary tree with N nodes can have?"

(defne max-height [n h h1 n1]
  ([n h h1 n1]
   (fd/> n1 n)
   (is h h1 dec)) ;;non-relational
  ([n h h1 n1]
   (fd/<= n1 n)
   (fresh [h2 n2]
     (is h2 h1 inc)
     (min-nodes h2 n2)
     (max-height n h h2 n2))))

"Now, we can attack the main problem: construct all the height-balanced binary trees with a given nuber of nodes."

(defne num-nodes [t n]
  ([nil 0])
  ([[_ l r] n]
   (fresh [nl nr]
     (num-nodes l nl)
     (num-nodes r nr)
     (fd/in nl nr n (fd/interval 0 Integer/MAX_VALUE))
     (fd/eq (= (+ 1 nl nr) n)))))

(defne min-height [n h]
  ([0 0])
  ([n h]
   (fresh [n1 h1]
     (fd/in n1 (fd/interval 0 Integer/MAX_VALUE))
     (fd/> n 0)
     (project [n n1]
              (== (quot n 2) n1)) ;; non-relational
     (min-height n1 h1)
     (fd/+ h1 1 h))))


(defn hbal-tree-nodes [n t]
  (fresh [hmin hmax h]
    (min-height n hmin)
    (max-height n hmax 1 1)
    (fd/>= h hmin)
    (fd/<= h hmax)
    (hbal-tree h t);; requires solution to P59
    (num-nodes t n)))

(defn all-hbal-trees [n]
  (run* [q]
    (hbal-tree-nodes n q)))

Usage:

ninety-nine-clojure.bintrees> (min-hbal-nodes 4)
7
ninety-nine-clojure.bintrees> (all-hbal-trees 4 )
([x [x [x nil nil] nil] [x nil nil]] [x [x nil nil] [x [x nil nil] nil]] [x [x nil [x nil nil]] [x nil nil]] [x [x nil nil] [x nil [x nil nil]]])

Read more about this series.