Haskell Data Analysis Cookbook

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