CODEWITHSUNDEEP
haskellbinary-tree
Xeriotek
Xeriotek

Reputation: 53

What's wrong with my isElement function (binary tree)?

I'm working on a a function that check whether an element is part of a binary tree. I've defined a type for my tree called Tree, functions to get the root element and the left and right subtrees, and a function called isElement for checking whether a value is into my tree. Unfortunately, the function only works with the root element.

The following example illustrates the incorrect results I get from my isElement function:

*Main>let tree = Node 1 Empty (Node 2 Empty (Node 3 Empty Empty))
*Main> isElement  tree 2
False
*Main> isElement  tree 3
False
*Main> isElement  tree 1
True

This is my code:

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

nodeValue :: Tree t -> t
nodeValue (Node x _ _) = x

rightTree :: Tree t -> Tree t
rightTree (Node _ _ x) = x

leftTree :: Tree t -> Tree t
leftTree (Node _ x _) = x

isNode ::  Tree t -> Bool 
isNode (Node _ _ _) = True
isNode _ = False

isElement :: (Eq t) => Tree t -> t -> Bool
isElement tree t
    |isNode tree == False = False 
    | nodeValue(tree) == t = True
    | otherwise = (isElement (leftTree(tree)) t) || (isElement (leftTree(tree)) t)

Upvotes: 2

Views: 320

Answers (1)

jub0bs
jub0bs

Reputation: 66244

There is a mistake in the definition of your isElement function: you're calling leftTree twice, instead of calling both leftTree and rightTree. As a result, right subtrees are never explored. Amend the code accordingly,

isElement tree t
    |isNode tree == False = False 
    | nodeValue(tree) == t = True
    | otherwise = (isElement (leftTree(tree)) t) || (isElement (rightTree(tree))

and then isElement works as advertised:

λ> let tree = Node 1 Empty (Node 2 Empty (Node 3 Empty Empty))
λ> isElement tree 2
True
λ> isElement tree 3
True
λ> isElement tree 1
True

However, there is still room for improvement. You don't really need all those functions (isNode, nodeValue, etc.) to define isElement. Instead, you can do all that unpacking with pattern matching, by breaking down the definition into two equations: one corresponding to the case where the tree is empty, and another corresponding to the case where the tree is a node:

isElement :: (Eq a) => Tree a -> a -> Bool
isElement Empty        _ = False
isElement (Node v l r) x = v == x || isElement l x || isElement r x

Edit: as pointed out by Luis Casillas in his comment, an additional benefit of this alternative definition is that it lends itself better (than the original definition) to exhaustiveness checking by the compiler.

Upvotes: 8

Related Questions