[Haskell-beginners] Finding the height of a simple binary tree

[Krzysztof Skrzętnicki]

I made a typo: since Node is labeled we need to match against ternary
constructor:


height Empty = 0 -- Height of the Empty Node is zero.
height (Node _ t1 t2) = 1 + (max (height t1) (height t2)) -- Height of a non
empty node is = 1 + (the greater height of its 2 sub trees)


2009/12/25 Krzysztof Skrzętnicki <gtener at gmail.com>

> The code is also extremely simple:
>
> height Empty = 0 -- Height of the Empty Node is zero.
> height (Node t1 t2) = 1 + (max (height t1) (height t2)) -- Height of a non
> empty node is = 1 + (the greater height of its 2 sub trees)
>
> Regards
>
>
>
> On Fri, Dec 25, 2009 at 02:34, Rahul Kapoor <rk at trie.org> wrote:
>
>> See if this case analysis helps:
>>
>> Height of the Empty Node is zero.
>> Height of a non empty node is = 1 + (the greater height of its 2 sub
>> trees)
>>
>> The function max gives you the greater of two values.
>>
>> HTH
>> Rahul
>>
>> On Thu, Dec 24, 2009 at 8:18 PM, Matt Young <mabufo at gmail.com> wrote:
>> > Hi guys! Just so we are all on the same page, this problem is an
>> > exercise from the end of Chapter 3 in the book Real World Haskell
>> > (#8).
>> >
>> > The problem calls for me to write a function to figure out the height
>> > of our user defined binary tree type.
>> > Here is the type:
>> >  --chapter3 binary tree recursive type
>> > data Tree a = Node a (Tree a) (Tree a)
>> >                          | Empty
>> >                                deriving (Show)
>> > With this type, we'd create a tree with no leaves like: Node "tree"
>> > Empty Empty, and a tree with a single leaf like Node "tree2" = Empty
>> > (Node "leaf" Empty Empty)
>> >
>> > Being new to Haskell, I'm not sure how to traverse this binary tree
>> > type that the book has given. No doubt we'll be using some crafty
>> > recursion to get this done. So to summarize what I'd like to know, 1)
>> > what is the best way to figure out the height of this binary tree type
>> > that I have, or rather any binary tree in general? 2) How do I
>> > translate that into Haskell code.
>> >
>> > Verbose explanations are appreciated.
>> >
>> > Thanks guys!
>> >
>> >
>> > --
>> > -Matthew
>> > _______________________________________________
>> > Beginners mailing list
>> > Beginners at haskell.org
>> > http://www.haskell.org/mailman/listinfo/beginners
>> >
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20091224/31a4e839/attachment-0001.html