Book Image

Haskell Data Analysis Cookbook

By : Nishant Shukla
Book Image

Haskell Data Analysis Cookbook

By: Nishant Shukla

Overview of this book

Table of Contents (19 chapters)
Haskell Data Analysis Cookbook
About the Author
About the Reviewers

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,...