rwh_ch03_08.hs

data Node a = Node a (Node a) (Node a) | Empty

treeHeight :: Node a -> Int
treeHeight Empty = 0
treeHeight tree = treeHeightImpl [(1, tree)] 1
  where
    treeHeightImpl :: [ (Int, (Node a)) ] -> Int -> Int
    treeHeightImpl ((currentDepth, (Empty)) : xs) maxDepth = treeHeightImpl xs maxDepth
    treeHeightImpl [] maxDepth = maxDepth
    treeHeightImpl ((currentDepth, (Node _ left right)) : xs) maxDepth = 
      treeHeightImpl (newQueue xs left right currentDepth) (max currentDepth maxDepth)
        where newQueue old left right depth = old ++ [ (newPair left depth), (newPair right depth)]
          where newPair node depth = (depth + 1, node)