CODEWITHSUNDEEP
haskelltreebinary-treebinary-search-treepredicate
Jayyyyyy
Jayyyyyy

Reputation: 197

Binary search tree predicate with helper functions

data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
deriving Show

type BSTree a = BinaryTree a

treeBSMax :: (Ord a) => BSTree a -> a
treeBSMax   btree = case btree of
        Null -> error
        Node _ val Null -> val
        Node _ val right -> treeBSMax right

treeBSMin :: (Ord a) => BSTree a -> a
treeBSMin btree = case btree of
       Null -> error
       Node Null val _ -> val
       Node left val _ -> treeBSMax left

isBSTree :: (Ord a) => BinaryTree a -> Bool
isBSTree btree = case btree of
      Null -> False
      Node Null val Null -> True
      Node lt val rt -> val >  treeBSMin lt && val < treeBSMax rt

How can I use treeBSMin and treeBSMax as helper functions of isBSTree to find whether a tree is a binary search tree?

Upvotes: 0

Views: 286

Answers (1)

Will Ness
Will Ness

Reputation: 71119

To use them as helper functions you need to first remove partiality from your code by using Maybe:

treeBSMax :: (Ord a) => BSTree a -> Maybe a
treeBSMax   btree = case btree of
        Null -> Nothing
        Node _ val Null -> Just val
        Node _ val right -> treeBSMax right

treeBSMin :: (Ord a) => BSTree a -> Maybe a
treeBSMin btree = case btree of
       Null -> Nothing
       Node Null val _ -> Just val
       Node left val _ -> treeBSMin left

isBSTree :: (Ord a) => BinaryTree a -> Bool
isBSTree btree = case btree of
      Null -> True                       -- changed it!
      Node Null val Null -> True
      Node lt val rt -> isBSTree lt       -- these two lines
                        && isBSTree rt     -- were missing !!
                        && inOrder (treeBSMax lt) val (treeBSMin rt)
                 where
                 inOrder Nothing  _ Nothing   =  True
                 inOrder Nothing  v (Just y)  =  v <= y
                 inOrder (Just x) v Nothing   =  x <= v
                 inOrder (Just x) v (Just y)  =  x <= v && v <= y

This is not efficient of course. (why is left as an exercise)

Upvotes: 1

Related Questions