Maximum tree depth in Haskell

Question

I am given this type definition:

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

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

In the future, please show any attempt you've made to solve the problem you are experiencing. Stackoverflow is a place to get help with a specific problem, not a place to get someone to write your code for you. — bheklilr, Jan 20 '14 at 17:03
Can this tree type hold 2 elements? Can we remove an element from a 3-element tree? We either have to add `Branch1 Char Tree` there, or just have `Empty` after all. — Will Ness, Jan 21 '14 at 09:51

score 2 · Accepted Answer · answered Jan 20 '14 at 16:44

2

You would want to write a recursive function to do this. For each Tree constructor, you'll need a different case in your function. To start with, 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'll let you finish the rest of the function. You could do it a few different ways as well (such as using max instead of maximum).

answered Jan 20 '14 at 16:44

bheklilr

53,530
6
107
163

Typically, a leaf would have depth `0`, not `1`. – kosmikus Jan 20 '14 at 16:50
3

@kosmikus In this case a leaf contains data. This definition of a tree does not include an empty branch. If I were counting the number of `Char`s stored in this tree, I would say there's one in a `Leaf`, so my opinion is that it should be how I've defined it. – bheklilr Jan 20 '14 at 16:58
I don't see what the presence of data or the desire to count the number of characters has to do with it. The depth of a node is usually the minimum path length to the root. If the tree is a single leaf, then the leaf is the root, and the path has length `0`. – kosmikus Jan 20 '14 at 17:56
3

@kosmikus Then we're talking about two different measurements. I would say that `Leaf 'a'` has height 1 and `Branch2 'a' (Leaf 'b') (Leaf 'c') has height 2. If `Tree` had an `Empty` constructor, I would say that `Empty` has height 0. You instead are measuring the difference between the height of the root element (always 1) and the height of the tallest branch, so we will always disagree by 1. – bheklilr Jan 20 '14 at 18:21
@kosmikus a root node is at depth 0 but the length of a path containing one root node (whether a leaf or a branch) is 1. An `Empty` tree contains no nodes, so its depth is 0. But whether to count Leafs as nodes is probably a matter of opinion - do we primarily deal with the branching aspect of the trees, or with the data-carrying aspect. I.e. do we distinguish btwn empty and 1-element trees. -- BTW this data type definition is deficient, it can't represent trees with 2 data elements in them (nor with 0). `Empty` constructor should be present as well (and then `Leaf` becomes redundant). – Will Ness Jan 21 '14 at 09:45
Let's just agree to disagree. To me, a leaf containing a label is atomic and contains no path (none that would belong to the tree structure, at least). I've actually never seen a definition which assigns a single node depth 1 before, but it seems I'm outvoted here, so let's leave it at that. (And yes, I agree that the definition of the tree here is strange in itself.) – kosmikus Jan 21 '14 at 09:51
@kosmikus "agree to disagree" yes of course. :) Your take entirely makes sense when we primarily concern ourselves with the tree *structure*. ... 2-to-1 is too small a pool to be "outvoted" really. :) – Will Ness Jan 21 '14 at 09:54
@kosmikus I wanted to try to make my point a little more clear. I think [these](http://imgur.com/a/4jp0L) images might be able to explain my stance a bit better than I can in words. You'll have to excuse my poor MSPaint skills, but the general gist is that if you have `Empty` and no `Leaf a` constructor, measuring height as you suggested gives you multiple trees that can have height 0, whereas measuring it by the number of elements with data along the longest path including root does not. Not trying to argue or "out vote", just friendly discussion =) – bheklilr Jan 21 '14 at 13:49
@bheklilr I think you're misunderstanding me. Your first picture contains the correct depths / heights for the situation where there's `Empty` and no `Leaf a`; there's no question about that. The lower picture doesn't make sense to me. (Why would you not count the path between a `Branch2` and an `Empty` node?) I just wouldn't treat `Empty` different from `Leaf a` in terms of depth. Both are leaves of the tree IMHO, both nodes are at depth `0`. – kosmikus Jan 21 '14 at 14:15

Will Ness · Answer 2 · 2014-01-20T17:55:00.953

1

with lazy corecursive breadth-first tree traversal:

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 _ l   r) : p) = (d+1,l) : (d+1,r) : gen (len + 1) p 
    gen len ((d,Branch3 _ l c r) : p) = (d+1,l) : (d+1,c) : (d+1,r) : gen (len + ??) p

changing it to the depth-first traversal will turn it into a regular recursion.

edited Jan 20 '14 at 17:55

answered Jan 20 '14 at 17:42

Will Ness

70,110
9
98
181

@ChrisTaylor either this, or the recursive, depth-first code, [depending on tree shape](http://stackoverflow.com/a/21216809/849891) if it is known in advance. :) – Will Ness Jan 20 '14 at 19:12

score 1 · Answer 3 · answered Jan 20 '14 at 18:47

1

I'd probably write a tail-recursive solution by using continuation passing.

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

answered Jan 20 '14 at 18:47

Chris Taylor

46,912
15
110
154

I believe that it works, but I never see something like that^^. Can you explain it? – Chryb Jan 20 '14 at 19:14
@Chryb look [here](http://stackoverflow.com/a/21205572/849891) for the explanations. – Will Ness Jan 20 '14 at 19:14

score 0 · Answer 4 · answered Jan 20 '14 at 16:56

0

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))

Is that right? Sorry i'm not so good in recursive programming.

answered Jan 20 '14 at 16:56

Chryb

547
1
12
34

This code doesn't compile. The syntax `max((depth(left) + 1) (depth(right) + 1))` is incorrect. The recommended style is to only use parentheses when grouping a subexpression that is to be a single argument to another function, and to avoid parentheses when they are redundant. You could instead write it as `max (depth left + 1) (depth right + 1)` – bheklilr Jan 20 '14 at 17:01
2

`max (max a b) c` is the same as `maximum [a,b,c]`. – Will Ness Jan 20 '14 at 17:51

Maximum tree depth in Haskell

4 Answers4

Linked