Haskell, Tree problems

Question

data Tree a = Empty_Tree
 | Node {element :: a, left_tree, right_tree :: Tree a}
 deriving (Eq)
biep :: (Ord a) => Tree a -> Bool
biep tree = case tree of
 Empty_Tree -> True
 Node e left right ->
 (left == Empty_Tree || (e < element left && biep left )) &&
 (right == Empty_Tree || (e > element right && biep right))

The above codes can compile correctly. What can you say about a tree if biep tree returns True?

Answer 1

biep returns True if an in-order traversal of the tree yields a strictly decreasing sequence.

If the tree is empty, this claim is vacuously true - the sequence is empty, hence strictly decreasing. However, if it is not empty, then we need to check a couple of things

• that the left child (if it exists) has a larger value than the current node
• that the right child (if it exists) has a smaller value than the current node
• that both children's trees also obey the order property

Hope that helps!

Answer 2

Hopefully I was able to rewrite it correctly:

biep :: (Ord a) => Tree a -> Bool
biep Empty_Tree = True
biep (Node e left right) = (ibiep left e (<) )&& (ibiep right e (>))
                          where ibiep Empty_Tree _ _ = True
                                ibiep n@(Node en _ _) val op = ( e `op` en  ) && (biep n)

You must include brackets when using data constructors.