How can I check if a BST is valid?

Question

How can I check if a BST is a valid one, given its definition and using a generalized version of fold for BST?

data(Ord a, Show a, Read  a) => BST a = Void | Node {
    val :: a,
    left, right :: BST a
} deriving (Eq,  Ord,  Read, Show)


fold :: (Read a, Show a, Ord a) => (a -> b -> b ->  b) -> b -> BST a -> b
fold _ z Void         = z
fold f z (Node x l r) = f x (fold f z l) (fold f z r)

The idea is to check that a node value is greater then all values in left-subtree and smaller than all values in its right-subtree. This must be True for all nodes in the tree. A function bstList simply output the list of (ordered) values in the BST.

Of course something like this won't work:

--isBST :: (Read a, Show a, Ord a) => BST a -> Bool
isBST t = fold (\x l r -> all (<x) (bstList l) && all (>x) (bstList r)) (True) t

because, for example, applying the fold function to the node 19 ends up all (<19) (bstList True) && all (>19) (bstList True).

Answer 1

Your problem seems to be that you lose information because your function only returns a boolean when it examines the left and right subtrees. So change it to also return the minimum and maximum values of the subtrees. (This is probably more efficient as well, since you don't need to used bslist to check all elements anymore)

And make a wrapper function to ignore these "auxiliary" values after you are done, of course.