Verifying the order property of a binary search tree

Given a binary tree, this recipe will cover how to verify if it actually satisfies the order property such that all elements in the left subtree are of lesser value, and that all values of the right subtree are of greater value.

Getting ready

We will be verifying whether or not the following tree is a binary search tree:

How to do it...

No imports are necessary for this recipe. Perform the following steps to find if the tree is a binary search tree:

1. Define a data structure for a binary tree:

   data Tree a = Node { value  :: a
                      , left  :: (Tree a)
                      , right :: (Tree a)}
               | Null
       deriving (Eq, Show)

2. Construct a tree based on the preceding diagram:

   someTree :: Tree Int
   
   someTree = root  
     where root = Node 0 n1 n4
           n1   = Node 1 n2 n3
           n2   = Node 2 Null Null
           n3   = Node 3 Null Null
           n4   = Node 4 Null Null

3. Define the function to verify whether or not a tree obeys the binary...