Book Image

Haskell Data Analysis Cookbook

By : Nishant Shukla
Book Image

Haskell Data Analysis Cookbook

By: Nishant Shukla

Overview of this book

Table of Contents (19 chapters)
Haskell Data Analysis Cookbook
Credits
About the Author
About the Reviewers
www.PacktPub.com
Preface
Index

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...