module Lab09b where

data IntTree = ILeaf Int | INode IntTree IntTree

instance Show IntTree where
  show (ILeaf n) = "<Leaf " ++ show n ++ "/>"
  show (INode left right) = "<Node>" ++ show left ++ show right ++ "</Node>"

data Tree a = Leaf a | Node (Tree a) (Tree a)

tree :: Tree Char
tree = Node (Node (Leaf 'a') (Node (Leaf 'b') (Leaf 'c'))) (Leaf 'd')

instance (Show a) => Show (Tree a) where
  show (Leaf x) = "<Leaf " ++ show x ++ "/>"
  show (Node left right) = "<Node>" ++ show left ++ show right ++ "</Node>"

treeDepth :: Tree a -> Int
treeDepth (Leaf x) = 1
treeDepth (Node l r) = 1 + max (treeDepth l) (treeDepth r)

labelTree :: Tree a -> Tree (a, Int)
labelTree t = fst (go 0 t)
  where
    go :: Int -> Tree a -> (Tree (a, Int), Int)
    go start (Leaf x) = (Leaf (x, start), start + 1)
    go start (Node l r) = let (newLeft, rightStart) = go start l
                              (newRight, nextStart) = go rightStart r
                          in (Node newLeft newRight, nextStart)