Haskell maximum tree depth

Question

I have been given a definition of this type:

data Tree = Leaf Char | Branch2 Char Tree Tree | Branch3 Char Tree Tree Tree 

How can I write a method that gives me the maximum length of a tree path (counting nodes in a path)?

Answer 1

You want to write a recursive function for this. For each Tree constructor, you will need a different case in your function. For starters, you know that the depth of any Leaf is 1 , so

 maxDepth :: Tree -> Int maxDepth (Leaf _) = 1 maxDepth (Branch2 c left right) = maximum [???] maxDepth (Branch3 c left center right) = maximum [???] 

I will let you finish the rest of the function. You could do this in several different ways (for example, use max instead of maximum ).

Answer 2

with lazy walkthrough walkthrough tree :

 treedepth tree = fst $ last queue where queue = (1,tree) : gen 1 queue gen 0 p = [] gen len ((d,Leaf _ ) : p) = gen (len - 1) p gen len ((d,Branch2 _ lr) : p) = (d+1,l) : (d+1,r) : gen (len + 1) p gen len ((d,Branch3 _ lcr) : p) = (d+1,l) : (d+1,c) : (d+1,r) : gen (len + ??) p 

changing it to bypass depth will turn it into regular recursion.

Answer 3

I would probably write a recursive solution using continue transfer.

 depth :: Tree -> Int depth t = go t id where go (Leaf _) k = k 0 go (Branch2 _ lr) k = go l $ \dl -> go r $ \dr -> k (1 + max dl dr) go (Branch3 _ lmr) k = go l $ \dl -> go m $ \dm -> go r $ \dr -> k (1 + max dl (max dm dr)) 

Answer 4

 depth :: Tree -> Int depth (Leaf _) = 1 depth (Branch2 c left right) = max((depth(left) + 1) (depth(right) + 1)) depth (Branch3 c left center right) = max(max((depth(left) + 1) (depth(right) + 1)) (depth(center) + 1)) 

It is right? Sorry, I'm not so good at recursive programming.