How to find the height of a binary tree in Haskell

Overview

Haskell is a functional programming language. It is used to change the data through expressions that don’t have side effects. These expressions are called pure functions.

Let’s learn how to implement a pure function that finds the height of a binary tree.

Recursive solution

We use recursion to find the height of a binary tree. The height of a leaf node and an empty tree is zero.

We use the following algorithm:

  • If the tree is empty, return -1.
  • Use recursion to find the height of the left and right subtree.
  • Return the maximum of the two and add 1 for the current node.

Example

-- Define the datatype
data IntTree = Nil | Node IntTree IntTree Int
mytree :: IntTree
-- Create the tree
mytree = Node (Node (Node Nil Nil 5) Nil 6) (Node Nil Nil 8) 7
-- definition of the height function
height :: IntTree -> Int
height = \t ->
    case t of
        -- return -1 if the tree is empty
        Nil -> -1
        -- height of the left subtree is greater than the right subtree
        Node l r _ | height l > height r -> height l + 1
        
        -- height of the right subtree is greater than the left subtree
        Node _ r _ -> height r + 1
main = print (height mytree)

Explanation

  • Line 2: Nil represents an empty tree. Node represents two subtrees of type IntTree and an integer value. myTree populates the tree.

  • Line 8: height :: IntTree -> Int is the type annotation for our function called height. It is a function that takes an IntTree and returns an Int, which is the height of the tree.

  • Line 9: Our function takes an IntTree t, a case expression that implements our recursive formulation of the problem.

  • Line 12: The first equation tells if IntTree is Nil and returns -1.

  • Line 15: The second equation tells us that for an IntTree, which is a Node and the height of the left subtree is greater than the right subtree, it then returns the height of the left subtree + 1.

  • Line 18: The third equation implements the final case, which means that the height of the right subtree is greater than the left subtree. Hence, it returns the height of the right subtree + 1.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)