Suma de las hojas de mínimo nivel

José A. Alonso

20-12-2017

Los árboles binarios con valores en las hojas y en los nodos se definen por

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
  deriving (Eq, Show)

Por ejemplo, el árbol

     1
   /   \
  2     3
 / \   / \
4   5 6   7
   / \
  8   9

se pueden representar por

ejArbol :: Arbol Int
ejArbol = N 1 (N 2 (H 4)
                   (N 5 (H 8) (H 9)))
              (N 3 (H 6) (H 7))

En el árbol anterior, los valores de las hojas de menor nivel son 4, 6 y 7 cuya suma es 17.

Definir la función

suma :: Num t => Arbol t -> t

tal que (suma a) es la suma de los valores de las hojas de menor nivel del árbol a. Por ejemplo,

suma ejArbol                                    ==  17
suma (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7)))  ==  22
suma (N 1 (H 2) (N 3 (H 6) (H 7)))              ==  2
suma (N 1 (H 2) (H 3))                          ==  5
suma (H 2)                                      ==  2

Soluciones

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
  deriving (Eq, Show)

ejArbol :: Arbol Int
ejArbol = N 1 (N 2 (H 4)
                   (N 5 (H 8) (H 9)))
              (N 3 (H 6) (H 7))

suma :: Num t => Arbol t -> t
suma a = aux [a]
  where aux as | null xs   = aux (concat [[i,d] | (N _ i d) <- as])
               | otherwise = sum xs
          where xs = [x | (H x) <- as]