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

Hey Matt, What generally helps is to lay out the pattern of heights you'd observe. a1 = Empty -- would be a tree with height of 0. a2 = Node 'a' Empty Empty -- would be a tree with height of 1. a3 = Node 'a' (Node 'b' (Node 'c' Empty Empty) Empty) (Node 'd' Empty Empty) -- would be a tree with height of 3 Using these 3 facts you could construct a function to traverse the tree recursively where the height at a particular node is 1 + the max height between the left and right sub-trees. Thanks! - Dinesh. On Thu, 24 Dec 2009 19:18 -0600, "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