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

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

t4 :: BTree Int
t4 = Node 1 (Node 2 (Node 4 Empty Empty) Empty) (Node 3 Empty Empty)

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

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

deepestFromTheLeft :: BTree Int -> Int
deepestFromTheLeft t@(Node value left Empty) = deepestFromTheLeft left == last
    where
        last = getLevel t k

deepestFromTheRight :: BTree Int -> Int
deepestFromTheRight t@(Node value Empty right) = deepestFromTheRight right == last
    where
        last = getLevel t k

deepestLeavesSum :: BTree Int -> Int
deepestLeavesSum Empty = 0
deepestLeavesSum (Node value Empty Empty) = value
deepestLeavesSum t@(Node value left right) = deepestFromTheLeft t + deepestFromTheRight t