99 questions/Solutions/58
< 99 questions | Solutions
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
(**) 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