Write Scheme functions that implement integer binary search trees. A non-empty binary search tree can be represented as a list of three entries. The first entry is a node's value (an integer), the middle is the node's left subtree, and the last is a node's right subtree. Non-empty left and right subtrees are themselves lists of three elements. An empty tree is represented as an empty list. For example, the list
(5 () ())
represents a tree whose only node is the leaf 5. The list
(5 (3 () (4 () ()) ) ())
represents the tree whose root node is 5 and has only one child, a left child, 3: this left child has only one child, a right child, 4. In a binary search tree it is always the case that values in the left subtree are less than the root's value, and values in the right subtree are greater than the root's value. You may assume that a binary search tree that is given to you will never have duplicate entries, but you will need to make sure when inserting a new entry that it is not a duplicate.
Write the following functions:
(null-bst)
Return an empty tree.
(null-bst? bst)
Return true (#t) if bst is empty, and
false (#f) otherwise.
(entry bst)
(left bst)
(right bst)
These functions return the node, left subtree, and right subtree,
respectively, of bst. If bst is empty or if
bst does not contain three entries where the last two are
lists, return #f.
(make-bst elt left right)
This function returns a new tree whose root node is elt,
left subtree is left, and right subtree is
right. You should check that elt is in fact a
number, and that left and right are either empty
lists or lists of three elements each where the last two are
lists. Return #f is the input is bad.
(preorder bst)
Return a list containing all values in bst in the order
obtained from a preorder traversal (visit the root of
bst, then do a preorder traversal of the left subtree, then
do a preeorder traversal of the right subtree).
(inorder bst)
Return a list containing all values in bst in the order
obtained from an inorder traversal (do an inorder traversal of the
left subtree, then visit the root of bst, then do an
inorder traversal of the right subtree).
(postorder bst)
Return a list containing all values in bst in the order
obtained from a postorder traversal (do a postorder traversal of the
left subtree, then do a postorder traversal of the right subtree,
then visit the root of bst).
(insert v bst)
Return a new binary search tree identical to bst
but with integer v appearing in its proper location. The
tree pointed to by bst should not change. Smaller values
are inserted to the left of a node, larger values to the right of a
node. If v is already in the tree, just return the original
tree without changing it. You may assume that bst and all
its subtrees are valid binary search trees.
You must use recursion, and not iteration. You may not use side-effects (e.g. set!).
Submit your code in a file called bst.rkt.