1. Write Java code for a class which implements a Binary Search Tree. The class should extend a KeyedItem class. Write Java code to insert the following data items in the binary search tree:




• Insert: 40, 30, 55


2. Write Java code for a constructor for a BinarySearchTree Class. The constructor should create a new BinarySearchTree with a root node containing one data item of type KeyedItem. Assume a KeyedItem class. The BinarySearchTree class extends BinaryTreeBasis abstract class. A constructor for the BinaryTreeBasis class has the following declaration:

public BinaryTreeBasis(Object rootItem);

3. Comment the following code excerpt for deleting a data item in a binary search tree.

protected TreeNode deleteItem(TreeNode tNode,

Comparable searchKey) {

// COMMENTS

TreeNode newSubtree;

if (tNode == null) {

throw new TreeException("TreeException: Item not found");

}

else {

// detailed comments

//

KeyedItem nodeItem = (KeyedItem)tNode.getItem();

//

if (searchKey.compareTo(nodeItem.getKey()) == 0) {

//

tNode = deleteNode(tNode); //

}

//

else if (searchKey.compareTo(nodeItem.getKey()) < 0) {

//

newSubtree = deleteItem(tNode.getLeft(), searchKey);

tNode.setLeft(newSubtree);

}

else { //

//

newSubtree = deleteItem(tNode.getRight(), searchKey);

tNode.setRight(newSubtree);

} // end if

} // end if

return tNode;

} // end deleteItem

 

 

4. Give pseudo code for the method:

Protected TreeNode deleteNode (Treenode tNode)

which deletes a node in a binary search tree where:

1. The tree is empty, there is a left child only, there is a right child only
2. The node has two children

Answer either a) or b)

 

 

5. Write pseudocoede for a class NewTreeNode which has as members:

• A data item
• A left reference to a NewTreeNode
• A right reference to a NewTreeNode
• Any of the following:
• A constructor which creates a new node which is the parent of two other nodes passed as references to the constructor.
• A method to return the data item in a node.
• A method to set the left reference of a node.
• A method to return the left reference of a node.

6. Using the BinarySearchTree in Figure 1:

Show the effect of deleting the following nodes. In each case use the tree altered by the previous deletion.

• Delete 2
• Delete 18
• Delete 10

7. Write Java code for an inorder traversal of a Binary Search Tree.