Skip to content

Instantly share code, notes, and snippets.

@willnet

willnet/balanced_binary_trees.hs

Created August 21, 2012 08:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save willnet/3413488 to your computer and use it in GitHub Desktop.
Save willnet/3413488 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
balanced_binary_trees.hs
-- http://www.haskell.org/haskellwiki/99_questions/54A_to_60
-- Problem 55
data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
leaf x = Branch x Empty Empty
cbalTree :: Int -> [Tree Char]
cbalTree 0 = [Empty]
cbalTree n = let (q, r) = (n - 1) `quotRem` 2
in [Branch 'x' left right | i <- [q..(q+r)]
, left <- cbalTree i
, right <- cbalTree (n - 1 - i)
]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment