Calculating the height of a tree

The height of a tree is the length of the longest downward path from the root node. For example, the height of a balanced binary tree should be around log to the base 2 of the number of nodes.

Getting ready

As long as we're consistent, the height of a tree can be defined as either the number of nodes or the number of edges in the longest path. In this recipe, we will count by using the number of nodes. The longest path of this tree contains three nodes and two edges. Therefore, this tree has a height of three units.

How to do it...

1. Import the maximum function from Data.List and the built-in tree data structure from Data.Tree:

   import Data.List (maximum)
   import Data.Tree

2. Define a function to calculate the height of a tree:

   height :: Tree a -> Int
   
   height (Node val []) = 1
   height (Node val xs) = 1 + maximum (map height xs)

3. Construct a tree on which we will run our algorithm:

   someTree :: Tree Integer
   
   someTree = root
     where root = 0 [n1, n4]
           n1   = 1 [n2,...