{- |
Description: Binary trees
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P54" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P54 (Tree, leaf, tree1, tree2, tree3, tree4) where

import           Problems.BinaryTrees

-- | Define a shorthand function for constructing a leaf node.
--
-- A leaf node in 'Tree' is a branch with two empty subtrees.
leaf :: a -> Tree a
leaf :: forall a. a -> Tree a
leaf a
x = a -> Tree a -> Tree a -> Tree a
forall a. a -> Tree a -> Tree a -> Tree a
Branch a
x Tree a
forall a. Tree a
Empty Tree a
forall a. Tree a
Empty

-- | Define as the tree as shown in the following.
--
-- !['b' and 'c' are children of 'a', 'd' and 'e' are children of 'b', 'f' is the right child of 'c', 'g' is the left child of 'f'](images/BinaryTrees/tree1.svg)
tree1 :: Tree Char
tree1 :: Tree Char
tree1 = Char -> Tree Char -> Tree Char -> Tree Char
forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'a' (Char -> Tree Char -> Tree Char -> Tree Char
forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'b' (Char -> Tree Char
forall a. a -> Tree a
leaf Char
'd') (Char -> Tree Char
forall a. a -> Tree a
leaf Char
'e'))
                   (Char -> Tree Char -> Tree Char -> Tree Char
forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'c' Tree Char
forall a. Tree a
Empty (Char -> Tree Char -> Tree Char -> Tree Char
forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'f' (Char -> Tree Char
forall a. a -> Tree a
leaf Char
'g') Tree Char
forall a. Tree a
Empty))

-- | Define as a binary tree consisting of only a single root node with value @\'a\'@.
tree2 :: Tree Char
tree2 :: Tree Char
tree2 = Char -> Tree Char
forall a. a -> Tree a
leaf Char
'a'

-- | Define as an empty binary tree.
tree3 :: Tree Char
tree3 :: Tree Char
tree3 = Tree Char
forall a. Tree a
Empty

-- | Define as the following tree with integer values.
--
-- ![Two nodes with both values of 2 are children of 1, 4 is the right child of the left 2](images/BinaryTrees/tree4.svg)
tree4 :: Tree Int
tree4 :: Tree Int
tree4 = Int -> Tree Int -> Tree Int -> Tree Int
forall a. a -> Tree a -> Tree a -> Tree a
Branch Int
1 (Int -> Tree Int -> Tree Int -> Tree Int
forall a. a -> Tree a -> Tree a -> Tree a
Branch Int
2 Tree Int
forall a. Tree a
Empty (Int -> Tree Int
forall a. a -> Tree a
leaf Int
4)) (Int -> Tree Int
forall a. a -> Tree a
leaf Int
2)