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

    print $ size numberBTree == 9
    print $ size charBTree == 7

    print $ sumTree numberBTree == 146
    print $ sumTree charBTree -- should not work

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

    print $ getLevel numberBTree 2 == [1, 0, 2, 5]
    print $ getLevel charBTree 1 == "al"
    print $ getLevel charBTree 3 == []

    print $ traverseBFS numberBTree == [5,12,4,1,0,2,5,96,21]
    print $ traverseBFS charBTree == "kalhsel"

    print $ mapTree numberBTree (*2) == Node 10 (Node 24 (Node 2 (Node 192 Nil Nil) Nil) (Node 0 Nil Nil)) (Node 8 (Node 4 Nil Nil) (Node 10 Nil (Node 42 Nil Nil)))
    print $ mapTree numberBTree (show) == Node "5" (Node "12" (Node "1" (Node "96" Nil Nil) Nil) (Node "0" Nil Nil)) (Node "4" (Node "2" Nil Nil) (Node "5" Nil (Node "21" Nil Nil)))
    print $ mapTree charBTree (toUpper) == Node 'K' (Node 'A' (Node 'H' Nil Nil) (Node 'S' Nil Nil)) (Node 'L' (Node 'E' Nil Nil) (Node 'L' Nil Nil))

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

numberBTree :: BTree Int
numberBTree = Node 5 (Node 12 (Node 1 (Node 96 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))

size :: (Ord a) => BTree a -> a
size Empty = 0
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)

sumTree :: (Ord 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)

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

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)

-- first way for traverseBFS

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

traverseBFS' :: (Ord a) => BTree a -> a
traverseBFS' tree = bfs[tree]
    where
        bfs :: [a] -> [a]
        bfs xs = map Nodevalue xs + bfs (leftAndRightNodes xs)

        Nodevalue :: BTree a -> a
        Nodevalue (Node value _ _) = value

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

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

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

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

constructMaxBTree :: [a] -> BTree a
constructMaxBTree xs = Node m (constructMaxBTree $ takeWhile (/=m) xs) (constructMaxBTree $ tail $ takeWhile (/=m) xs)

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 Empty [10,5,15,3,7,18]

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

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


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' (Node value Empty Empty) = [value]
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


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

data NTree a = Empty | Node a [(NTree a)]

-- t1 :: NTree Int
-- t1 = Node 10 [Node 10 [Node 10 [Empty], Node 8 [Node 10 [Empty]], Node 2 [Empty]], Node 10 [Node 11 [Empty], Node 10 [Empty], Node 8 [Empty]]]

t :: NTree Int
t = Node 10 [Node 3 [Node 5 [Empty], Node 8 [Node 1 [Empty], Node 2 [Empty]], Node 9 [Empty]], Node 7 [Node 11 [Empty], Node 13 [Empty]], Node 12 [Node 6 [Empty], Node 4 [Empty]]]

size :: NTree a -> a
size Empty = 0
size (Node value _) = 1
size (Node _ children) = 1 + (sum $ map size children)

getLevel :: NTree a -> a -> [a]
getLevel Empty _ = []
getLevel (Node value _) 0 = [value]
getLevel (Node value children) k = getLevel (\c -> getLevel c (k-1)) children