-- # Software Tools for Discrete Mathematics

module Stdm05Trees where

-- # Chapter 5.  Trees

data Tree a
  = Tip
  | Node a (Tree a) (Tree a)
  deriving (Show)

-- |
-- >>>
t1 :: Tree Int
t1 = Node 6 Tip Tip

-- |
-- >>>
t2 :: Tree Int
t2 =
  Node
    5
    (Node 3 Tip Tip)
    (Node 8 (Node 6 Tip Tip) (Node 12 Tip Tip))

-- |
-- >>>
nodeCount :: Tree a -> Int
nodeCount Tip = 0
nodeCount (Node x t1 t2) = 1 + nodeCount t1 + nodeCount t2

-- |
-- >>>
reflect :: Tree a -> Tree a
reflect Tip = Tip
reflect (Node a t1 t2) = Node a (reflect t2) (reflect t1)

-- |
-- >>>
mapTree :: (a -> b) -> Tree a -> Tree b
mapTree f Tip = Tip
mapTree f (Node a t1 t2) =
  Node (f a) (mapTree f t1) (mapTree f t2)

-- |
-- >>>
tree :: Tree (Int, Int)
tree =
  Node
    (5, 10)
    ( Node
        (3, 6)
        (Node (1, 1) Tip Tip)
        (Node (4, 8) Tip Tip)
    )
    ( Node
        (7, 14)
        (Node (6, 12) Tip Tip)
        (Node (8, 16) Tip Tip)
    )

-- |
-- >>>
find :: Int -> Tree (Int, a) -> Maybe a
find n Tip = Nothing
find n (Node (m, d) t1 t2) =
  if n == m
    then Just d
    else
      if n < m
        then find n t1
        else find n t2