Hey all.. I was wondering if somebody might offer me some assistance in
trying to debug some code I wrote to check whether a tree is a binary
search tree.. For some reason it always comes back as false! :( Thanks
much!
-Andrew Sitzer
> isBST :: Ord a => Tree a -> Bool
> isBST thetree
> | isNil thetree = True
> | ((not (isNil (leftSub thetree))) && (not (isNil (rightSub
thetree)))) = ((isBST (leftSub thetree)) && (isBST (rightSub thetree)) &&
checkL && checkR)
> | otherwise = False
> where
> checkL = ((treeVal (leftSub thetree)) < (treeVal (thetree)))
> checkR = ((treeVal (rightSub thetree)) > (treeVal (thetree)))
Explanation of what I think/am trying to do :)
1) If current node is empty then this portion of tree is a BST
2) if the left subtree and right subtree's are both not empty then
make sure the following conditions are true / return the && of them
all:
a) check if left is a binary search tree
b) check if right is a binary search tree
c) check that the value in the left subtree's highest position is
less then the current node's value
d) check that the value in the right subtree's highest position
greater then the current node's value
