Solution to https://github.com/geophf/1HaskellADay/blob/master/exercises/HAD/Y2017/M06/D07/Exercise.hs

HAD_Y2017_M06_D07_Solution.hs

module Y2017.M06.D07.Exercise where

{--
So, here's one of the questions Amazon asks developers to test their under-
standing of data structures.

You have a binary tree of the following structure:

        A
       / \
      /   \
     B     C
    / \   / \
   D   E F   G

1. create the BinaryTree type and materialize the above value.
--}

data Sym = A | B | C | D | E | F | G | H | I | J | K | L | M | N | O
   deriving (Eq, Ord, Enum, Bounded, Show)

data Node a = Bin a (Node a) (Node a) | Leaf a
   deriving (Eq, Show)

abcdefg :: Node Sym
abcdefg = Bin A (Bin B (Leaf D) (Leaf E)) (Bin C (Leaf F) (Leaf G))

{--
Now, you want to traverse the external nodes in a clockwise direction. For the
above binary tree, a clockwise Edge Node traversal will return:
--}

clockwiseSmallTree :: [Sym]
clockwiseSmallTree = [A, C, G, F, E, D, B]

-- define

-- 1. Take the right half of the tree
-- 2. Collect all right nodes (edge ones)
-- 3. Collect all leaves from left nodes (inner ones)
-- 4. Repeat for flipped left half of the tree
clockwiseEdgeTraversal :: Node a -> [a]
clockwiseEdgeTraversal (Leaf val) = [val]
clockwiseEdgeTraversal (Bin val left right) = [val] ++ traversal right ++ (reverse . traversal . flipTree $ left)
  where traversal (Leaf v)    = [v]
        traversal (Bin v l r) = [v] ++ traversal r ++ collectLeaves l
        collectLeaves (Leaf v) = [v]
        collectLeaves (Bin _ l r) = collectLeaves r ++ collectLeaves l
        flipTree (Bin v l r) = Bin v (flipTree r) (flipTree l)
        flipTree n = n
{--
such that:

>>> clockwiseEdgeTraversal abcdefg == clockwiseSmallTree
True
--}

{-- BONUS -----------------------------------------------------------------

Simple enough, eh?

Now, does it work for the larger tree?

                     A
                   /   \
                  /     \
                 /       \
               B           C
             /   \       /   \
            D     E     F     G
           / \   / \   / \   / \
          H   I J   K L   M N   O
--}

largerTree :: Node Sym
largerTree = Bin A
              (Bin B
                (Bin D (Leaf H) (Leaf I))
                (Bin E (Leaf J) (Leaf K)))
              (Bin C
                (Bin F (Leaf L) (Leaf M))
                (Bin G (Leaf N) (Leaf O)))

-- the EDGE clockwise traversal is thus:

largerClockwiseTraversal :: [Sym]
largerClockwiseTraversal = [A, C, G, O, N, M, L, K, J, I, H, D, B]

{--
n.b.: as E and F are internal nodes, not edge nodes, they are NOT part of
the traversal.

so:

>>> clockwiseTraversal largerTree == largerClockwiseTraversal
True

Got it?
--}