main :: IO ()
main = do
    print $ numberBTree
    print $ charBTree

    print $ size numberBTree == 9

    print $ sumTree numberBTree == 146

    print $ traverseDFS numberBTree == [96, 1, 12, 0, 5, 2, 4, 5, 21]

    print $ traverseDFS numberBTree == [96, 1, 12, 0, 5, 2, 4, 5, 21]

    print $ getLevel numberBTree 2 == [1, 0, 2, 5]

    print $ mapTree numberBTree (*2) == Node 10 (Node 24 (Node 2 (Node 192 Empty Empty) Empty) (Node 0 Empty Empty)) (Node 8 (Node 4 Empty Empty) (Node 10 Empty (Node 42 Empty Empty)))

    print $ insert (Node 10 (Node 5 (Node 3 Nil Nil) (Node 7 Nil Nil)) (Node 15 Nil (Node 18 Nil Nil))) 13 == (Node 10 (Node 5 (Node 3 Nil Nil) (Node 7 Nil Nil)) (Node 15 (Node 13 Nil Nil) (Node 18 Nil Nil)))

    print $ (numberTreeAfter == numberTreeBefore) == True

    print $ secondNumberTree == Node 10 (Node 5 (Node 3 (Node 1 Nil Nil) Nil) (Node 7 (Node 6 Nil Nil) Nil)) (Node 15 (Node 13 Nil Nil) (Node 18 Nil Nil))

    print $ isBinarySearchTree t3 == True
    print $ isBinarySearchTree t4 == False
    print $ isBinarySearchTree t5 == False
    print $ isBinarySearchTree t6 == False

data BTree a = Empty | Node a (BTree a) (BTree a)
    deriving (Show, Eq)

-- first part

numberBTree :: BTree Int
numberBTree = Node 5 (Node 12 (Node 1 (Node 96 Empty Empty) Empty) (Node 0 Empty Empty)) (Node 4 (Node 2 Empty Empty) (Node 5 Empty (Node 21 Empty Empty)))

charBTree :: BTree Char
charBTree = Node 'k' (Node 'a' (Node 'h' Empty Empty) (Node 's' Empty Empty)) (Node 'l' (Node 'e' Empty Empty) (Node 'l' Empty Empty))

-- second part

size :: (Ord a, Num a) => BTree a -> a
size (Node value Empty Empty) = 1
size (Node value left Empty) = 1 + (size left)
size (Node value Empty right) = 1 + (size right)
size (Node value left right) = 1 + (size left) + (size right)

-- third part

sumTree :: (Ord a, Num a) => BTree a -> a
sumTree Empty = 0
sumTree (Node value Empty Empty) = value
sumTree (Node value left Empty) = value + (sumTree left)
sumTree (Node value Empty right) = value + (sumTree right)
sumTree (Node value left right) = value + (sumTree left) + (sumTree right)

-- forth part

traverseDFS :: (Ord a, Num a) => BTree a -> [a]
traverseDFS Empty = []
traverseDFS (Node value Empty Empty) = [value]
traverseDFS (Node value left Empty) = (traverseDFS left) ++ [value]
traverseDFS (Node value Empty right) = [value] ++ (traverseDFS right)
traverseDFS (Node value left right) = (traverseDFS left) ++ [value] ++ (traverseDFS right)

-- fifth part

traverseBFS :: (Ord a, Num a) => BTree a -> [a]
traverseBFS tree = tbf [tree]
    where
        tbf :: [Int] -> [Int]
        tbf [] = []
        tbf xs = map nodeValue xs ++ tbf (concat (map leftAndRightNodes xs))

        nodeValue :: (Ord a, Num a) => BTree a -> a
        nodeValue (Node value _ _) = value

        leftAndRightNodes :: (Ord a, Num a) => BTree a -> [a]
        leftAndRightNodes (Node _ Empty Empty) = []
        leftAndRightNodes (Node _ left Empty) = [left]
        leftAndRightNodes (Node _ Empty right) = [right]
        leftAndRightNodes (Node _ left right) = [left, right]

-- second way for traverseBFS

traverseBFS' :: (Ord a, Num a) => BTree a -> [a]
traverseBFS' t = concat $ takeWhile (/=[]) $ map (getLevel t) [0 .. ]

-- sixth part

getLevel :: (Ord a) => (BTree a) -> [a]
getLevel (Node value Empty Empty) 0 = [value]
getLevel (Node value left right) k = getLevel left (k - 1) ++ getLevel right (k-1)

-- seventh part

mapTree :: (Ord a) => (BTree a) -> BTree a
mapTree Empty _ = Empty
mapTree (Node value left right) = Node (f value) (f left) (f right)

-- second task

data BTree a = Empty | Node a (BTree a) (BTree a)
    deriving (Show, Eq)

t1 :: BTree Int
t1 = Node 6 (Node 3 Empty (Node 2 Empty (Node 1 Empty Empty))) (Node 5 (Node 0 Empty Empty) Empty)

constructMaxBTree :: (Ord a, Num a) => [a] -> BTree a
constructMaxBTree xs = Node m (constructMaxBTree $ takeWhile (/=m) xs) (constructMaxBTree $ tail $ takeWhile (/=m) xs)
    where m = maximum xs

-- third task

data BTree a = Empty | Node a (BTree a) (BTree a)
    deriving (Show, Eq)

numberTreeBefore :: BTree Int
numberTreeBefore = Node 10 (Node 5 (Node 3 Empty Empty) (Node 7 Empty Empty)) (Node 15 Empty (Node 18 Empty Empty))

numberTreeAfter :: BTree Int
numberTreeAfter = foldl insert Empty [10,5,15,3,7,18]

secondNumberTree :: BTree Int
secondNumberTree = foldl insert [10,5,15,3,7,13,18,1,6]

insert :: (Ord a) => BTree a -> a -> BTree a
insert Empty _ = Empty
insert (Node value left right) k
    | k > value = Node value left (right k)
    | otherwise = Node value (left k) right

-- forth task

data BTree a = Empty | Node a (BTree a) (BTree a)
    deriving (Show, Eq)

t3 :: BTree
t3 = Node 8 (Node 3 (Node 1 Nil Nil) (Node 6 (Node 4 Nil Nil) (Node 7 Nil Nil))) (Node 10 Nil (Node 14 (Node 13 Nil Nil) Nil))

t4 :: BTree
t4 = Node 8 (Node 3 (Node 5 Nil Nil) (Node 6 Nil Nil)) (Node 10 Nil (Node 14 Nil Nil))

t5 :: BTree
t5 = Node 8 (Node 3 (Node 2 Nil Nil) (Node 6 Nil Nil)) (Node 10 Nil (Node 1 Nil Nil))

t6 :: BTree
t6 = Node 8 (Node 3 (Node 1 Nil Nil) (Node 4 Nil Nil)) (Node 10 (Node 5 Nil Nil) Nil)

traverseDFS :: (Ord a) => (BTree a) -> [a]
traverseDFS Empty = []
traverseDFS (Node value left right) = (traverseDFS left) ++ [value] ++ (traverseDFS right)

isBinarySearchTree :: (Ord a) => (BTree a) -> Bool
isBinarySearchTree t = nodes == sort nodes
    where
        nodes = traverseDFS t

-- is tree symetric

data BTree = Empty | Node Int BTree BTree
    deriving (Show, Eq)

t1 :: BTree Int
t1 = Node 1 (Node 2 Empty Empty) (Node 3 Empty Empty)

t2 :: BTree Int
t2 = Node 1 (Node 2 (Node 3 Empty Empty) Empty) (Node 2 Empty (Node 3 Empty Empty))

t3 :: BTree Int
t3 = Node 1 (Node 2 (Node 3 Empty Empty) (Node 7 (Node 5 Empty Empty) Empty)) (Node 2 (Node 7 Empty (Node 5 Empty Empty) (Node 3 Empty Empty)))

isSymetric :: (Ord a) => (BTree a) -> Bool
isSymetric Empty = False
isSymetric (Node value left right) = traverseDFS left == (reverse $ traverseDFS right)

traverseDFS :: (Ord a) => BTree a -> [a]
traverseDFS Empty = []
traverseDFS (Node value left right) = (traverseDFS left) ++ [value] ++ (traverseDFS right)