# Difference between revisions of "99 questions/Solutions/58"

From HaskellWiki

< 99 questions | Solutions

(another solution) |
|||

Line 2: | Line 2: | ||

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

+ | |||

+ | An efficient solution, which takes the fact that a tree with an even number of nodes can't be symmetric into consideration: |
||

+ | |||

+ | <haskell> |
||

+ | symCbalTrees n = if n `mod` 2 == 0 then [] else [ Branch 'x' t (reverseTree t) | t <- cbalTree (n `div` 2)] |
||

+ | |||

+ | reverseTree Empty = Empty |
||

+ | reverseTree (Branch x l r) = Branch x (reverseTree r) (reverseTree l) |
||

+ | </haskell> |
||

+ | |||

+ | Or a simple, but less efficient one: |
||

<haskell> |
<haskell> |

## Revision as of 03:34, 25 August 2012

(**) Generate-and-test paradigm

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

An efficient solution, which takes the fact that a tree with an even number of nodes can't be symmetric into consideration:

```
symCbalTrees n = if n `mod` 2 == 0 then [] else [ Branch 'x' t (reverseTree t) | t <- cbalTree (n `div` 2)]
reverseTree Empty = Empty
reverseTree (Branch x l r) = Branch x (reverseTree r) (reverseTree l)
```

Or a simple, but less efficient one:

```
symCbalTrees = filter symmetric . cbalTree
```