Παρασκευή, 9 Απριλίου 2010 10:51 πμ
napoleon
Find max height of bin Tree
There is a need to find the height of a binary tree. Meaning beginning from root (0), the maximum hopes to "highest" leaf.
Having the definition:
data Tree a = Node a (Tree a) (Tree a) | Empty
showing a Tree could be a node with two (node or empty ) or empty, the following recursive algorithm takes six lines of code in Haskell:
height tree = tall tree 0
where tall node h = case node of
Empty -> h
Node _ left right -> if l > r then l else r
where l = tall left (h + 1)
r = tall right (h +1)
After, I found that:
treeHeight :: Tree a -> Int
treeHeight Empty = 0
treeHeight (Node _ t1 t2) = 1 + max (treeHeight t1) (treeHeight t2)