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

[Brent Yorgey]

On Thu, Dec 24, 2009 at 07:18:37PM -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)

It seems that you are perhaps a little confused about values of this
type.  First of all, I would say that the value

  Node "tree" Empty Empty

is a tree with one node, which is a leaf.  A leaf is any node with no
children --- as you can see this node's children are both Empty.  The
only tree with no leaves is the Empty tree.

Also, this:

  Empty (Node "leaf" Empty Empty)

is a type error.  Empty cannot be applied to (Node "leaf" Empty
Empty), since it is a constructor that takes no arguments.  I am not
sure what tree you had in mind.

Did the other replies help you figure out how to find the height of a
tree or would you like more detailed explanation?

-Brent