(In Java please)

1) modify BinarySearchTree to:

a) Extend the Binary Search Tree ADT to include a basic public method getRoot that returns a reference to the root of the tree. If the tree is empty, the method should return null.

b) Extend the Binary Search Tree ADT to include a public method leafCount that returns the number of leaf nodes in the tree.

c) Extends the Binary Search Tree ADT to include a public method singleParentCount that returns the number of nodes in the tree that have only one child.

2) The Binary Search Tree ADT is extended to include a boolean method similarTrees that receives references to two binary trees and determines whether the shapes of the trees are the same. (The nodes do not have to contain the same values but each node must have the same numbers of children.)

a) write the declaration of the similarTrees method. Include adequate comments.

b) Write the body of the similarTrees method.

//----------------------------------------------------------------------------

// BinarySearchTree.java by Dale/Joyce/Weems Chapter 8

//

// Defines all constructs for a reference-based BST

//----------------------------------------------------------------------------

package ch08.trees;

import ch05.queues.*;

import ch03.stacks.*;

import support.BSTNode;

public class BinarySearchTree>

implements BSTInterface

{

protected BSTNode root; // reference to the root of this BST

boolean found; // used by remove

// for traversals

protected LinkedUnbndQueue inOrderQueue; // queue of info

protected LinkedUnbndQueue preOrderQueue; // queue of info

protected LinkedUnbndQueue postOrderQueue; // queue of info

public BinarySearchTree()

// Creates an empty BST object.

{

root = null;

}

public boolean isEmpty()

// Returns true if this BST is empty; otherwise, returns false.

{

return (root == null);

}

private int recSize(BSTNode tree)

// Returns the number of elements in tree.

{

if (tree == null)

return 0;

else

return recSize(tree.getLeft()) + recSize(tree.getRight()) + 1;

}

public int size()

// Returns the number of elements in this BST.

{

return recSize(root);

}

public int size2()

// Returns the number of elements in this BST.

{

int count = 0;

if (root != null)

{

LinkedStack> hold = new LinkedStack>();

BSTNode currNode;

hold.push(root);

while (!hold.isEmpty())

{

currNode = hold.top();

hold.pop();

count++;

if (currNode.getLeft() != null)

hold.push(currNode.getLeft());

if (currNode.getRight() != null)

hold.push(currNode.getRight());

}

}

return count;

}

private boolean recContains(T element, BSTNode tree)

// Returns true if tree contains an element e such that

// e.compareTo(element) == 0; otherwise, returns false.

{

if (tree == null)

return false; // element is not found

else if (element.compareTo(tree.getInfo()) < 0)

return recContains(element, tree.getLeft()); // Search left subtree

else if (element.compareTo(tree.getInfo()) > 0)

return recContains(element, tree.getRight()); // Search right subtree

else

return true; // element is found

}

public boolean contains (T element)

// Returns true if this BST contains an element e such that

// e.compareTo(element) == 0; otherwise, returns false.

{

return recContains(element, root);

}

private T recGet(T element, BSTNode tree)

// Returns an element e from tree such that e.compareTo(element) == 0;

// if no such element exists, returns null.

{

if (tree == null)

return null; // element is not found

else if (element.compareTo(tree.getInfo()) < 0)

return recGet(element, tree.getLeft()); // get from left subtree

else

if (element.compareTo(tree.getInfo()) > 0)

return recGet(element, tree.getRight()); // get from right subtree

else

return tree.getInfo(); // element is found

}

public T get(T element)

// Returns an element e from this BST such that e.compareTo(element) == 0;

// if no such element exists, returns null.

{

return recGet(element, root);

}

private BSTNode recAdd(T element, BSTNode tree)

// Adds element to tree; tree retains its BST property.

{

if (tree == null)

// Addition place found

tree = new BSTNode(element);

else if (element.compareTo(tree.getInfo()) <= 0)

tree.setLeft(recAdd(element, tree.getLeft())); // Add in left subtree

else

tree.setRight(recAdd(element, tree.getRight())); // Add in right subtree

return tree;

}

public void add (T element)

// Adds element to this BST. The tree retains its BST property.

{

root = recAdd(element, root);

}

private T getPredecessor(BSTNode tree)

// Returns the information held in the rightmost node in tree

{

while (tree.getRight() != null)

tree = tree.getRight();

return tree.getInfo();

}

private BSTNode removeNode(BSTNode tree)

// Removes the information at the node referenced by tree.

// The user's data in the node referenced by tree is no

// longer in the tree. If tree is a leaf node or has only

// a non-null child pointer, the node pointed to by tree is

// removed; otherwise, the user's data is replaced by its

// logical predecessor and the predecessor's node is removed.

{

T data;

if (tree.getLeft() == null)

return tree.getRight();

else if (tree.getRight() == null)

return tree.getLeft();

else

{

data = getPredecessor(tree.getLeft());

tree.setInfo(data);

tree.setLeft(recRemove(data, tree.getLeft()));

return tree;

}

}

private BSTNode recRemove(T element, BSTNode tree)

// Removes an element e from tree such that e.compareTo(element) == 0

// and returns true; if no such element exists, returns false.

{

if (tree == null)

found = false;

else if (element.compareTo(tree.getInfo()) < 0)

tree.setLeft(recRemove(element, tree.getLeft()));

else if (element.compareTo(tree.getInfo()) > 0)

tree.setRight(recRemove(element, tree.getRight()));

else

{

tree = removeNode(tree);

found = true;

}

return tree;

}

public boolean remove (T element)

// Removes an element e from this BST such that e.compareTo(element) == 0

// and returns true; if no such element exists, returns false.

{

root = recRemove(element, root);

return found;

}

private void inOrder(BSTNode tree)

// Initializes inOrderQueue with tree elements in inOrder order.

{

if (tree != null)

{

inOrder(tree.getLeft());

inOrderQueue.enqueue(tree.getInfo());

inOrder(tree.getRight());

}

}

private void preOrder(BSTNode tree)

// Initializes preOrderQueue with tree elements in preOrder order.

{

if (tree != null)

{

preOrderQueue.enqueue(tree.getInfo());

preOrder(tree.getLeft());

preOrder(tree.getRight());

}

}

private void postOrder(BSTNode tree)

// Initializes postOrderQueue with tree elements in postOrder order.

{

if (tree != null)

{

postOrder(tree.getLeft());

postOrder(tree.getRight());

postOrderQueue.enqueue(tree.getInfo());

}

}

public int reset(int orderType)

// Initializes current position for an iteration through this BST

// in orderType order. Returns current number of nodes in the BST.

{

int numNodes = size();

if (orderType == INORDER)

{

inOrderQueue = new LinkedUnbndQueue();

inOrder(root);

}

else

if (orderType == PREORDER)

{

preOrderQueue = new LinkedUnbndQueue();

preOrder(root);

}

if (orderType == POSTORDER)

{

postOrderQueue = new LinkedUnbndQueue();

postOrder(root);

}

return numNodes;

}

public T getNext (int orderType)

// Preconditions: The BST is not empty

// The BST has been reset for orderType

// The BST has not been modified since the most recent reset

// The end of orderType iteration has not been reached

//

// Returns the element at the current position on this BST for orderType

// and advances the value of the current position based on the orderType.

{

if (orderType == INORDER)

return inOrderQueue.dequeue();

else

if (orderType == PREORDER)

return preOrderQueue.dequeue();

else

if (orderType == POSTORDER)

return postOrderQueue.dequeue();

else return null;

}

}

must include the code you used to verify that your BinarySearchTree modifications meet the requirements.