Запись рекурсивной функции для подсчета глубины дерева

Question

Мне нужно написать рекурсивную функцию, которая, учитывая тип данных дерева , вернет глубину дерева. Пустое дерево должно вернуть 0. Одно дерева корневого узла должно возвращать 1.

ожидается выход:

let treeCons x = (\x -> foldl (flip insertTree) Empty x) x 
depth (treeCons []) -> 0 
depth (treeCons [5,4,6,3,7,1]) -> 4 
depth (treeCons [1,2,5,8,9,4,7]) -> 5 
depth (treeCons [5,4,6,3,7,1,2,5,8,9,4,7,8,5,3,4]) -> 6 

Я написал следующий тип данных и вставить функцию:

data Tree a = Node a (Tree a) (Tree a) | Empty deriving (Show, Eq) 
insertTree :: (Ord a) => a -> Tree a -> Tree a 
insertTree a Empty = Node a Empty Empty 
insertTree a (Node b Empty Empty) = if (a <= b) then (Node b (Node a Empty Empty) Empty) else (Node b Empty (Node a Empty Empty)) 
insertTree a (Node b left right) = if (a <= b) then (Node b (insertTree a left) right) else (Node b left (insertTree a right)) 

Однако я Я не знаю, как написать функцию глубины. Я очень новый в haskell, и я буду признателен, если кто-то мне поможет.

Answer 1

Пустое дерево имеет глубину 0, и узел имеет глубину 1 плюс максимальную глубину его дочерних узлов:

depth :: Tree a -> Int 
depth Empty = 0 
depth (Node _ l r) = 1 + max (depth l) (depth r) 

Answer 2

Здесь вы идете, очень просто, рекурсии через список и дерево около то же самое, только типы данных различаются. Где вы добавляете 1 каждый раз, когда вы попадаете в ветвь дерева:

tDepth :: Tree a -> Int 
tDepth Empty = 0 
tDepth (Node _ left right) = 1 + max (tLength left) (tLength right)