Function that checks if binary tree is binary search tree

Question

I have to write a function that checks if binary tree is binary search tree. This is what I got, but it gives me types errors and I don't know how to fix them

isBinarySearchTree :: BTree Int -> Bool
isBinarySearchTree (Node v Empty Empty) = True
isBinarySearchTree (Node v lt rt) = isBinarySearchTree lt 
                                && isBinarySearchTree rt 
                                && (lt == Empty || max lt < v) 
                                && (rt == Empty || min rt > v)

This is the error

* Couldn't match expected type `BTree Int -> BTree Int'
              with actual type `Int'
* In the second argument of `(<)', namely `v'
  In the second argument of `(||)', namely `max lt < v'
  In the first argument of `(&&)', namely
    `(lt == Empty || max lt < v)'

                                 && (lt == Empty || max lt < v) 

                                                             ^
* Couldn't match expected type `BTree Int -> BTree Int'
              with actual type `Int'
* In the second argument of `(>)', namely `v'
  In the second argument of `(||)', namely `min rt > v'
  In the second argument of `(&&)', namely
    `(rt == Empty || min rt > v)'

                                 && (rt == Empty || min rt > v)
                                                             ^

You need to write two functions that find the maximum and minimum elements, and you need to name them something other than "max" and "min". — molbdnilo
– molbdnilo, Commented Jun 3, 2020 at 12:12

molbdnilo · Accepted Answer · 2020-06-03 12:28:59Z

Let's have a look at the type of max:

Prelude> :t max
max :: Ord a => a -> a -> a

It takes two things that can be ordered (Ord a) and returns the largest of them.
(min has the same type.)

When you apply max to a BinTree Int, you get a function that wants another BinTree Int so it can determine which one is largest - max lt has the type BinTree Int -> BinTree Int.
And < needs two operands of the same type.

This is why the message says

expected type `BTree Int -> BTree Int'

which comes from max lt, and

actual type `Int'

which is the type of v.

(The type checker apparently uses the left-hand operand to determine what to "expect" for <, rather than the right).

You need to write two functions that determine the maximum and minimum elements of trees, and you need to not name them "max" and "min".

Implementing them left as an exercise.

(It's possible to avoid writing these by hand, but that's on a fairly advanced level, and this is probably meant to be an exercise in writing recursive functions.)

dfeuer · Accepted Answer · 2020-06-03 21:28:58Z

The easiest way to check is to make use of the following property:

A tree is a valid search tree if and only if its inorder traversal is (strictly) increasing.

I'm not going to try to prove this property, because that takes rather too much work. I'll just show how it works out in code.

data BTree a = Empty | Node a (BTree a) (BTree a)

inorder :: BTree a -> [a]
inorder t0 = go t0 []
  where
    -- This function takes a list representing the rest of
    -- the elements that come after the current subtree. This
    -- is a little trick to make the traversal run in linear time.
    go Empty rest = rest
    go (Node v l r) rest = go l (v : go r rest)

validBST :: Ord a => BTree a -> Bool
validBST = sorted . inorder

sorted :: Ord a => [a] -> Bool
sorted xs = and $ zipWith (<) xs (drop 1 xs)

Collectives™ on Stack Overflow

Function that checks if binary tree is binary search tree

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related