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

Matt Young mabufo at gmail.com
Thu Dec 24 20:18:37 EST 2009


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


More information about the Beginners mailing list