Leaf Trees - Height

Asked

Viewed 104 times

0

It is customary to define trees where information is only on extermidities (Leaf Trees):

data LTree a = Tip a | Fork (LTree a) (LTree a)

Define the following function about this type:

ltHeight :: LTree a -> Int calculating the height of a tree.

haskell

1 answer

0

Using recursiveness, usually the solution goes by considering:

  • Knotless tree (trivial case)
  • Node tree (recursive case)

The size of a tree without nodes, ie, just the leaf, is 0. How to calculate the size of a tree with multiple nodes? Simple, it is 1 plus the size of the sub-tree of higher height.

Knowing this, implementation is simple:

ltHeight :: LTree a -> Int
ltHeight (Tip l)    = 0                                 -- Caso trivial
ltHeight (Fork e d) = 1 + max (ltHeight e) (ltHeight d) -- 1 + altura da maior sub-arvore

Here is the link to an example:

Browser other questions tagged haskell

You are not signed in. Login or sign up in order to post.