How to check if node is a leaf in binary tree (Haskell)

Question

I need to check if a node is a leaf in my binary tree. This is my current code.

It sends me an error message saying: "hw3_71937.hs: C:\Users\lenovo\Desktop\���\��� HASKELL\hw3_71937.hs:(22,1)-(25,91): Non-exhaustive patterns in function isLeaf"

I do not know how to recursively check the next node if it is a leaf. Any help will be thanked.

Answer 1

The guard:

  | tree == Empty = False

can never be true, since in the head of your clause:

isLeaf node tree@(Node el left right)

you say that this is a Node, not an Empty. This is also the case that you did not cover: in case you pass an Empty (and eventually you can pass an Empty due to recursion), no pattern will match.

That being said, I think you make this too complicated. You can write this as:

isLeaf :: Eq a => a -> BTree a -> Bool
isLeaf _ Empty = False
isLeaf x (Node x' Empty Empty) = x == x'
isLeaf x (Node _ l r) = isLeaf x l || isLeaf x r

or with a where clause:

isLeaf :: Eq a => a -> BTree a -> Bool
isLeaf x = go
    where go Empty = False
          go (Node x' Empty Empty) = x == x'
          go (Node _ l r) = go l || go r