Question

1) Extend the Binary Search Tree ADT to include a public method leafCount that returns the number of leaf nodes in the tree.
2) Extend the Binary Search Tree ADT to include a public method singleParent-Count that returns the number of nodes in the tree that have only one child.
3) 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 number of children)
A) Write the declaration of the function similarTrees method. Include adequate comments.
B) Write the body of the function similarTrees method.

(Can you write the code using the JAVA language and also put the code to copy for each question? Thank you.)

Below, I also have attached the BinarySearchTree, the Interface File and BSTNode file. (the code is from the text)
BinarySearchTree:
//----------------------------------------------------------------------------
// 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;
}
}
BSTInterface:
//----------------------------------------------------------------------------
// BSTInterface.java by Dale/Joyce/Weems Chapter 8
//
// Interface for a class that implements a binary search tree (BST).
//
// The trees are unbounded and allow duplicate elements, but do not allow null
// elements. As a general precondition, null elements are not passed as
// arguments to any of the methods.
//
// The tree supports iteration through its elements in INORDER, PREORDER,
// and POSTORDER.
//----------------------------------------------------------------------------
package ch08.trees;
public interface BSTInterface>
{
// used to specify traversal order
static final int INORDER = 1;
static final int PREORDER = 2;
static final int POSTORDER = 3;
boolean isEmpty();
// Returns true if this BST is empty; otherwise, returns false.

int size();
// Returns the number of elements in this BST.
boolean contains (T element);
// Returns true if this BST contains an element e such that
// e.compareTo(element) == 0; otherwise, returns false.

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.

T get(T element);
// Returns an element e from this BST such that e.compareTo(element) == 0;
// if no such element exists, returns null.
void add (T element);
// Adds element to this BST. The tree retains its BST property.

int reset(int orderType);
// Initializes current position for an iteration through this BST
// in orderType order. Returns current number of nodes in the BST.
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.
}

Paekage "upport cooperable T Pub te cla a usmaadekr extende tuples Uend to held re ncea te sST medes for the d child node The intu a BST nose A link to the left A 13nk to the right child bode protected ESTNode right: public public void set nfolT info sets into of this BS public T get Infer Returns info of this BSTNode return info: publie vaid getLeft (BSTNode 1Ank) sete left link of thia BSTirode. left

                                

  

Answer 1

package ch08.trees;

import ch05.queues.*;
import ch03.stacks.*;
import support.BSTNode;    

public class BinarySearchTree<T extends Comparable<T>>
             implements BSTInterface<T>
{
protected BSTNode<T> root;      // reference to the root of this BST

boolean found;   // used by remove

// for traversals
protected LinkedUnbndQueue<T> inOrderQueue;    // queue of info
protected LinkedUnbndQueue<T> preOrderQueue;   // queue of info
protected LinkedUnbndQueue<T> 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<T> 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);
}

private int leafCount(BSTNode<T> tree){
      if (tree == null) return 0;
      if (tree.getLeft() == null && tree.getRight() == null) return 1;
      return leafCount(tree.getLeft()) + leafCount(tree.getRight());
}

public int leafCount() {
      return leafCount(root);
}

boolean similarTrees(BSTNode<T> tree1, BSTNode<T> tree2) {
      if (tree1 == null && tree2 == null) return true;
      if (tree1 == null && tree2 != null) return false;
      if (tree1 != null && tree2 == null) return false;
    
      boolean leftSimilarOrNot = similarTrees(tree1.getLeft(), tree2.getLeft());
      boolean rightSimilarOrNot = similarTrees(tree1.getRight(), tree2.getRight());
    
      return leftSimilarOrNot && rightSimilarOrNot;
}

public int size2()
// Returns the number of elements in this BST.
{
    int count = 0;
    if (root != null)
    {
      LinkedStack<BSTNode<T>> hold = new LinkedStack<BSTNode<T>>();
      BSTNode<T> 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<T> 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<T> 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<T> recAdd(T element, BSTNode<T> tree)
// Adds element to tree; tree retains its BST property.
{
    if (tree == null)
      // Addition place found
      tree = new BSTNode<T>(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<T> tree)
// Returns the information held in the rightmost node in tree
{
    while (tree.getRight() != null)
      tree = tree.getRight();
    return tree.getInfo();
}

private BSTNode<T> removeNode(BSTNode<T> 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<T> recRemove(T element, BSTNode<T> 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<T> 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<T> 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<T> 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<T>();
      inOrder(root);
    }
    else
    if (orderType == PREORDER)
    {
      preOrderQueue = new LinkedUnbndQueue<T>();
      preOrder(root);
    }
    if (orderType == POSTORDER)
    {
      postOrderQueue = new LinkedUnbndQueue<T>();
      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;
}
}

BSTInterface.java

package ch08.trees;

public interface BSTInterface<T extends Comparable<T>>
{
// used to specify traversal order
static final int INORDER = 1;
static final int PREORDER = 2;
static final int POSTORDER = 3;

boolean isEmpty();
// Returns true if this BST is empty; otherwise, returns false.

int size();
// Returns the number of elements in this BST.

boolean contains (T element);
// Returns true if this BST contains an element e such that
// e.compareTo(element) == 0; otherwise, returns false.
  
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.

T get(T element);
// Returns an element e from this BST such that e.compareTo(element) == 0;
// if no such element exists, returns null.

void add (T element);
// Adds element to this BST. The tree retains its BST property.

int reset(int orderType);
// Initializes current position for an iteration through this BST
// in orderType order. Returns current number of nodes in the BST.

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.
}