Week 13: Lab Document, 11/29


Here is Wikipedia's page on binary search trees. To implement a binary search tree, you should first define a Node class. Each binary tree node has, at the minimum, 3 fields: a key field, a leftChild field, and a rightChild field. The leftChild field and the rightChild field point to other Node objects. A binary search tree is a collection of Node objects satisfying the following binary search tree property: for any node x, x.key > y.key for all nodes y in the left subtree of x and x.key < y.key for all nodes y in the right subtree of x. In a typical implementation, the only access that we have to the nodes of a binary search tree is via the root of the tree. Thus the only data member that is essential to a BinarySearchTree class is a root, of type Node.

Problem: Based on this description and our class discussion, implement a Node class and a BinarySearchTree class. The BinarySearchTree class should provide, at the minimum, the operations search, insert, and delete.