# 99 problems in Haskell, 55-58

2015 Aug 01

### Problem 55: Construct completely balanced binary trees

``````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 »