Haskell: Compute the height of binary tree

The height of a tree is the number of edges on the longest path from the root to a leaf. A leaf node will have a height of 0.

To solve this problem, first we need to define a Tree structure. A tree should contains some data, has two pointer one should point to its left side and other should point to right side. Leaf node has left and right sub trees as Empty.

data Tree a = Node a (Tree a) (Tree a) | Empty deriving (Show)

For following tree, height of the tree should be 3.

treeUtil.hs

data Tree a = Node a (Tree a) (Tree a) 
             | Empty 
             deriving (Show)

heightOfTree :: Tree a -> Integer
heightOfTree Empty = 0
heightOfTree (Node a left rigth) = 1 + max (heightOfTree left) (heightOfTree rigth)

Following statements create above tree structure.

let node50 = Node 50 Empty Empty
let node40 = Node 40 Empty node50
let node20 = Node 20 Empty node40
let node30 = Node 30 Empty Empty
let node10 = Node 10 node30 node20

*Main> :load treeUtil.hs
[1 of 1] Compiling Main             ( treeUtil.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> let node50 = Node 50 Empty Empty
*Main> let node40 = Node 40 Empty node50
*Main> let node20 = Node 20 Empty node40
*Main> let node30 = Node 30 Empty Empty
*Main> let node10 = Node 10 node30 node20
*Main> 
*Main> heightOfTree node10
3
*Main> 
*Main> heightOfTree node20
2
*Main> 
*Main> heightOfTree node30
0
*Main> 
*Main> heightOfTree node40
1
*Main> 
*Main> heightOfTree node50
0
*Main> 

Previous                                                 Next                                                 Home