{- |
Description: Collect nodes of a binary tree
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P61" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P61 (leaves,internals) where

import           Problems.BinaryTrees

-- | Collect the leaves of a binary tree in a list.  A leaf is a node with no successors.
leaves :: Tree a -> [a]
leaves :: forall a. Tree a -> [a]
leaves Tree a
Empty                  = []
leaves (Branch a
x Tree a
Empty Tree a
Empty) = [a
x]
leaves (Branch a
_ Tree a
l Tree a
r)         = Tree a -> [a]
forall a. Tree a -> [a]
leaves Tree a
l [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ Tree a -> [a]
forall a. Tree a -> [a]
leaves Tree a
r

-- | Collect the internal nodes of a binary tree in a list.
internals :: Tree a -> [a]
internals :: forall a. Tree a -> [a]
internals Tree a
Empty                  = []
internals (Branch a
_ Tree a
Empty Tree a
Empty) = []
internals (Branch a
x Tree a
l Tree a
r)         = Tree a -> [a]
forall a. Tree a -> [a]
internals Tree a
l [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ Tree a -> [a]
forall a. Tree a -> [a]
internals Tree a
r