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.
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:
-1
.height
of the left and right subtree.1
for the current node.-- 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)
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.
RELATED TAGS
CONTRIBUTOR
View all Courses