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

[Matt Young]

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

[Rahul Kapoor]

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

[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

[Krzysztof Skrzętnicki]

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 <gte...@gmail.com>

[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

[has...@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.