-- Binary tree

data BiTree = Leaf {value :: Int} | BiTree { value :: Int, left, right :: BiTree }

-- Binary tree transformations

incValues :: BiTree -> BiTree
incValues (Leaf v) = Leaf (v+1)
incValues (BiTree v l r) = BiTree (v+1) (incValues l) (incValues r)

doubleValues :: BiTree -> BiTree
doubleValues (Leaf v) = Leaf (v*2)
doubleValues (BiTree v l r) = BiTree (v*2) (doubleValues l) (doubleValues r)

-- Unified transformation

mapTree :: (Int -> Int) -> BiTree -> BiTree
mapTree f (Leaf value) = Leaf (f value)
mapTree f (BiTree value left right) = BiTree (f value) (mapTree f left) (mapTree f right)

-- SearchTree

data SearchTree = EmptyTree | SearchTree Int SearchTree SearchTree

depth :: SearchTree -> Int
depth EmptyTree = 0
depth (SearchTree x t1 t2) = max (depth t1) (depth t2) + 1

-- дерево поиска  т.о. минимальный элемент в самом левом листе

minValue :: SearchTree -> Int
minValue(SearchTree i EmptyTree _ ) = i
minValue (SearchTree _ t1 _ ) = minValue t1

-- проверка наличия заданного числа в дереве

hasValue :: SearchTree -> Int -> Bool
hasValue EmptyTree _ = False
hasValue (SearchTree i t1 t2) x | i > x = hasValue t1 x
                                | i < x = hasValue t2 x
                                | otherwise = True

-- вставка в дерево

insertValue :: Int -> SearchTree -> SearchTree
insertValue x EmptyTree = SearchTree x EmptyTree EmptyTree
insertValue x t@(SearchTree i t1 t2)
                        | x<i = SearchTree i (insertValue x t1) t2  -- t { left = inSert i t1}
                        | x>i = SearchTree i t1 (insertValue x t2) -- t {right = inSert i t2}
                        | otherwise = t