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

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

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 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 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@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners