Determine if binary tree is BST haskell

Question

I'm trying to write a bool function to return True if a binary tree is a bst using recursion, and I need a little guidance on haskell syntax.

I understand that for a binary tree to be a bst, the left subtree must always contain only nodes less than the head. and the right subtree must always contain only nodes greater than the head. I was structuring my function as such:

isBST :: Tree -> Bool       --recieve Tree, return bool
isBST (Lead i) = True       --return true if its only one leaf in tree
isBST (Node h l r) = if (((isBST l) < h) && ((isBST r) > h)) then True else False   
--return true if left subtree < head AND right subtree > head

But this code results in the error:

Couldn't match expected type ‘Bool’ with actual type ‘Int’

Referring to the < h and > h parts specifically. Is it something wrong with my haskell formatting? Thanks in advance

Answer 1

Martin, I'd recommend you to look at Willem's answer.

Another thing, you could also use your maxInt function that you asked in a previous question to define this function:

isBST (Node h l r) = ... (maxInt l) ... -- at some point we will need to use this

Taking your definition of BSTs:

I understand that for a binary tree to be a bst, the left subtree must always contain only nodes less than the head. and the right subtree must always contain only nodes greater than the head.

I'll add that also the subtrees of a node should be BSTs as well.

So we can define this requirement with:

isBST (Node h l r) =
  ((maxInt l) < h) -- the left subtree must contain nodes less than the head
  && ((minInt r) > h) -- the right must contain nodes greater than the head
  && (...) -- the left subtree should be a BST
  && (...) -- the right subtree should be a BST

Recall that you might need to define minInt :: Tree -> Int, as you probably know how to do that.

Answer 2

Is it something wrong with my haskell formatting?

No, it is a semantical error. You write:

(isBST l) < h

So this means you ask Haskell to determine whether l is a binary search tree, which is True or False, but you can not compare True or False with h. Even if you could (some languages see True as 1 and False as 0), then it would still be incorrect, since we want to know whether all nodes in the left subtree are less than h.

So we will somehow need to define bounds. A way to do this is to pass parameters through the recursion and perform checks. A problem with this is that the root of the tree for example, has no bounds. We can fix this by using a Maybe Int is a boundary: if it is Nothing, the boundary is "inactive" so to speak, if it is Just b, then the boundary is "active" with value b.

In order to make this check more convenient, we can first write a way to check this:

checkBound :: (a -> a -> Bool) -> Maybe a -> a -> Bool
checkBound _ Nothing _ = True
checkBound f (Just b) x = f b x

So now we can make a "sandwich check" with:

sandwich :: Ord a => Maybe a -> Maybe a -> a -> Bool
sandwich low upp x = checkBound (<) low x && checkBound (>) upp x

So sandwich is given a lowerbound and an upperbound (both Maybe as), and a value, and checks the lower and upper bounds.

So we can write a function isBST' with:

isBST' :: Maybe Int -> Maybe Int -> Tree -> Bool
isBST' low upp ... = ....

There are two cases we need to take into account: the Leaf x case, in which the "sandwich constraint" should be satisfied, and the Node h l r case in which h should satisfy the "sandwich constraint" and furthermore l and r should satsify different sandwhich constraints. For the Leaf x it is thus like:

isBST' low upp (Leaf x) = sandwich low upp x

For the node case, we first check the same constraint, and then enforce a sandwich between low and h for the left part l, and a sandwich between h and upp for the right part r, so:

isBST' low upp (Node h l r) = sandwich low upp h &&
                              isBST' low jh l &&
                              isBST' jh upp r
    where jh = Just h

Now the only problem we still have is to call isBST' with the root element: here we use Nothing as intial bounds, so:

isBST :: Tree -> Bool
isBST = isBST' Nothing Nothing

There are of course other ways to enforce constraints, like passing and updating functions, or by implement four variants of the isBST' function that check a subset of the constraints.

Answer 3

I like Willem Van Onsem's pedagogical approach in his answer.

I was going to delete my answer, but am going to post a "correction" instead, at the risk of being wrong again:

data Tree = Empty | Node Int Tree Tree deriving show

isBST :: Tree -> Bool

isBST Empty = True
isBST (Node h l r) = f (<=h) l && f (>=h) r && isBST l && isBST r
   where
     f _ Empty = True
     f c (Node h l r) = c h && f c l && f c r

Note that I'm using Wikipedia's definition of BST, that

the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.