Finding the height of a binary tree in Haskell

Question

I have the folloing "height" function which returns the height of a tree. When I try to use it, however, I get this exception. How can I fix it? I also have the function "isBalancedTree" which checks if a given tree is balanced.

data Tree = Node Tree Int Tree | Leaf Int deriving Show

height :: Tree -> Integer
height (Node left x right) = 1 + max (height left) (height right)

isBalancedTree :: Tree -> Bool
isBalancedTree (Node left x right) = 
    let diff = abs (height left - height right) in
    diff <= 1 && isBalancedTree left && isBalancedTree right

*Main> height (Node (Node (Leaf 3) 4 (Leaf 2)) 5 (Node (Leaf 4) 7 (Leaf 6)))

*** Exception: Non-exhaustive patterns in function height

Turn on warnings with -Wall! The compiler will then point out the missing cases in your pattern matching. Strongly recommended. — chi
– chi, Commented Nov 16, 2017 at 10:38

lisyarus · Accepted Answer · 2017-11-16 10:31:26Z

1

Your recursive implementation of height is nice, but you have forgotten the base case of a single leaf:

height (Leaf _) = 1

This is the missing pattern that the exception is complaining about. The same applies to your second function isBalanced - you need a case for a Leaf, too:

isBalanced (Leaf _) = True -- assuming a single-leaf tree is trivially balanced

edited Nov 16, 2017 at 10:31

answered Nov 16, 2017 at 9:59

lisyarus

15.8k4 gold badges48 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

u23d7 Over a year ago

Thank you! I get the same exception for my second function. What is the problem with it?

lisyarus Over a year ago

@u23d7 The problem with the second function is exactly the same. I updated the answer.

Collectives™ on Stack Overflow

Finding the height of a binary tree in Haskell

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related