Problem 55: Construct completely balanced binary trees
We start with our own datatype,
data Tree t = Empty | Branch t (Tree t) (Tree t) deriving (Show, Eq)
We can build completely balanced trees in two ways: either we build all trees containing N nodes and filter out the unbalanced ones, or build trees from completely balanced subtrees. The second way is rather easy: since our invariant says the number of nodes of the left & right subtrees of each node differ at most by one, we’ll divide by 2 and conveniently the remainder is either 0 or 1.
cbal_tree :: Int -> [Tree Char] -- There are the base cases: cbal_tree 0 = [Empty] cbal_tree 1 = [Branch 'x' Empty Empty] -- The simpler case is when the number of nodes in both subtrees is even: cbal_tree n | n `mod` 2 == 1 = [ Branch 'x' l r | l <- cbal_tree ((n - 1) `div` 2), r <- cbal_tree ((n - 1) `div` 2) ] -- When the two subtrees differ by one node, (it holds for all that) the one is the mirror -- image of the other: | otherwise = concat [ [Branch 'x' l r, Branch 'x' r l] | l <- cbal_tree ((n - 1) `div` 2), r <- cbal_tree (n `div` 2) ]
Problem 56: Symmetric binary trees.
Following the problem statement:
symmetric :: Tree a -> Bool symmetric Empty = True symmetric (Branch _ l r) = mirror l r mirror :: Tree a -> Tree a -> Bool mirror Empty Empty = True mirror (Branch _ a b) (Branch _ x y) = mirror a y && mirror b x mirror _ _ = False
Problem 57: Binary search trees.
-- Building a BST is done in two stages. Start from the Empty tree, then add nodes -- according to its invariant: construct xs = foldl add Empty xs add :: Ord a => Tree a -> a -> Tree a add Empty n = Branch n (Empty) (Empty) -- We all know about the invariant of a BST: add t@(Branch e l r) n | n < e = Branch e (add l n) r | n > e = Branch e l (add r n) | otherwise = t
Problem 58 is solved by putting together our
symmetric functions in a
-- Problem 58: Generate-and-test paradigm. sym_cbal_trees = filter symmetric . cbal_tree