Lab 6 is due Thursday, November 9 at 11:59pm.

These lab exercises give you practice with binary search trees.

To begin, copy the following data definitions from this page. 

(define-struct (Pr A B)
  ([a : A]
   [b : B]))

(define-struct (Some A)
  ([value : A]))

(define-type (Optional A)
  (U 'None (Some A)))

(define-type (Compare A)
  (A A -> Boolean))

(define-type (BSTree A)
  (U 'E (Nd A)))

(define-struct (Nd A)
  ([root    : A]
   [count   : Integer]
   [lesser  : (BSTree A)]
   [greater : (BSTree A)]))

(define-struct (BST A)
  ([less-than : (Compare A)]
   [tree-data : (BSTree A)]))
This particular binary tree is a polymorphic data structure with integer counters at every node. By storing a less-than operation along with the tree in the BST struct, we are able to build binary search trees of any kind of data, ordered by that operation. Note that even though the operation in the BST struct is given the name less-than, any consistent order, including a greater-than operation, would suffice to build a consistent BST.

The first time an item is inserted into a tree, its counter is one, and every subsequent time that same item is inserted into the tree, the counter must be incremented, to reflect the fact that the tree now contains more than one of that item.

A word about writing tests for these functions. Check-expect and its counterparts are not able to compare functions with one another for equality. By extension, check-expect cannot compare BST values for equality, since that would entail comparing functions. Therefore, to test an operation that produces a BST, extract its BSTree and test against that. 

(: make-empty : All (A) (Compare A) -> (BST A))
;; produce an empty BST given an ordering function

(: singleton : All (A) (Compare A) A -> (BST A))
;; produce a singleton BST given an ordering function and one item

(: insert : All (A) A (BST A) -> (BST A))
;; insert item into tree

(: contains? : All (A) A (BST A) -> Boolean)
;; test if tree contains item

(: item-count : All (A) A (BST A) -> Integer)
;; return the number of this item in tree

(: num-nodes : All (A) (BST A) -> Integer)
;; count the number of _nodes_ in the tree

(: num-items : All (A) (BST A) -> Integer)
;; count the number of _items_ in the tree (>= the number of nodes)

(: directions-to : All (A) A (BST A) -> (Listof (U A 'LEFT 'RIGHT)))
;; return the path to the item and record of left/right turns
;; (example below)

(: from-list : All (A) (Compare A) (Listof A) -> (BST A))
;; build a BST from the items in the list

(: inorder : All (A) (BST A) -> (Listof A))
;; construct the inorder traversal of items in tree
;; items that appear k times in tree must appear k times in result
;; (example below)

(: min-item : All (A) (BSTree A) -> (Optional (Pr A Integer)))
;; return the minimum item in the tree and its count

To understand directions-to, please consider the following sketch of a tree. Assume the items are all strings and their counters, not depicted, are all 1. (Counters are irrelevant to this problem anyway.) 

     M
   /   \
  G     W
 / \   / \
A   J T   Y

For inorder, use the counters to determine how many times to produce each tree item in the resulting list. For example, if this is a tree of strings with the counters as shown, 

    N:2
   /   \
 H:1   X:3
the inorder traversal is (list "H" "N" "N" "X" "X" "X"). You may find the built-in function make-list helpful.

Please submit one file, lab6.rkt, in a lab6 directory in your repository.