99 Clojure Problems – 58: Generate-and-Test Paradigm

"Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.

How many such trees are there with 57 nodes? Investigate about how many solutions there are for a given number of nodes? What if the number is even? Write an appropriate function."

Example

>(symmetric-cbalanced-trees 5 'x)
([x [x nil [x nil nil]] [x [x nil nil] nil]] [x [x [x nil nil] nil] [x nil [x nil nil]]])

Discussion

A simple approach just filters the output of our existing function for completely balanced trees using the also existing symmetric? predicate.

A simple optimisation is to avoid the tree generation all together if the number of nodes requested is even, as there is no symmetric tree with an even number of nodes.

Solution on Github.

Read more about this series.