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 cbal_tree, symmetric functions in a
trivial manner:
-- Problem 58: Generate-and-test paradigm.
sym_cbal_trees = filter symmetric . cbal_tree