A binary search tree restricts an order property on a binary tree. This order property requires that among every node, the nodes in the left subtree must not be greater, and that the nodes in the right subtree must not be less than the current node.
Create a binary
BSTreemodule to expose our binary search tree data structure. Insert the following code in a file calledBSTree.hs:module BSTree (insert, find, single) where
Define the data structure for a binary tree:
data Tree a = Node {value :: a , left :: (Tree a) , right :: (Tree a)} | Null deriving (Eq, Show)Define a convenience function to create a one-node tree:
single :: a -> Tree a single n = Node n Null Null
Implement a function to insert new values in the binary search tree:
insert :: Ord a => Tree a -> a -> Tree a insert (Node v l r) v' | v' < v = Node v (insert l v') r | v' >...