99 problems in Haskell, 55-58

2015 Aug 01

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
« Past Future »

Comments:

comments powered by Disqus