"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.

## No comments:

Post a Comment