= Solution
Compute either the common depth of the <leaves of a rooted tree>, or failure when the depths differ. A <tree fold> can return a `Maybe Integer`: `Just h` means that the <rose tree> is a <perfect rose tree> with all leaves at depth $h$ relative to its root; `Nothing` means it is not perfect.
``
perfect :: RTree a -> Bool
perfect t =
case foldRTree step t of
Nothing -> False
Just _ -> True
where
step :: a -> [Maybe Integer] -> Maybe Integer
step _ [] = Just 0
step _ (Nothing : _) = Nothing
step _ (Just h : hs)
| all (== Just h) hs = Just (h + 1)
| otherwise = Nothing
``
A leaf has depth zero. An internal <vertex> has equally deep leaves exactly when every child <rose tree> is perfect and their returned depths agree; adding one accounts for the edge to each child. This proves the stated meaning of the result by <structural induction>. In particular, unary branching is allowed, and a single leaf is perfect. \b[`perfect` returns precisely the required Boolean.] Its <time complexity> is linear in the number of <vertices>, assuming unit-cost depth arithmetic; labels are never compared or evaluated.
Back to article page
