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