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

[haskell at dpillay.eml.cc]

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