[Haskell-beginners] Finding the height of a simple binary tree
Krzysztof Skrzętnicki
gtener at gmail.com
Thu Dec 24 20:47:10 EST 2009
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/4233e852/attachment.html
More information about the Beginners
mailing list