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?
biep
returnsTrue
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
Hope that helps!