Due to the changes, the original implementation of the following methods will no longer work. Please based on this change, make necessary changes to the following methods

public int size() //return the number of nodes

public Node parent(Node p) throws IllegalArgumentException //return the parent node for a node referred by p

Add and implement the following methods within the class:

public boolean isIdentical(Node p1, Node p2): check if two binary trees rooted at p1 and p2 are identical or not. i.e. if they have identical structure & their contents are also same. Return true for yes and false, otherwise.

public ArrayList> ancestors(Nodep1, Node p2): find all ancestors of a given node referred by p2 on a tree rooted at p1.

public Node findLCA(Node p1, Node p2): find lowest common ancestor (LCA) of p1 and p2 in it.

package simpleBinaryTree;

import java.util.ArrayList;

public class testClass {

public static void main(String[] args)

{

simpleLinkedBinaryTree myBtree = new simpleLinkedBinaryTree();

myBtree.addRoot(5);

Node left=myBtree.addLeft(myBtree.root(), 2);

myBtree.addLeft(left, 8);

myBtree.addRight(left, 10);

ArrayList> preorderList = myBtree.preorder();

for(Node p: preorderList)

System.out.print(p.getElement()+"\t");

System.out.println();

System.out.println("Number of Node on the tree:\t"+myBtree.size());

simpleLinkedBinaryTree oBtree = myBtree;

System.out.println("Those two trees are identical:\t"+myBtree.isIdentical(myBtree.root, oBtree.root));

System.out.println("The parent node of "+ left.getElement() +"\t is" + myBtree.parent(myBtree.root, left));

ArrayList ancestorlist = myBtree.ancestors(myBtree.root, left.getLeft());

for(Integer i: ancestorlist) System.out.print(i+"\t");

}

}

-----------------------------------------------------------------

package simpleBinaryTree;

import java.util.ArrayList;

public class simpleLinkedBinaryTree> {

protected Node root = null; // root of the tree

public simpleLinkedBinaryTree() { }//constructor_Construts an empty binary tree.

// Returns the root of the tree (or null if tree is empty).

public Node root() {

return root;

}

public boolean isEmpty() { return root == null; }

public int numChildren(Node p) {

int count=0;

if(p.getLeft()!=null) count++;

if(p.getRight()!=null) count++;

return count;

}

public ArrayList> children(Node p) {

ArrayList> snapshot = new ArrayList<>(2); // max capacity of 2

if (left(p) != null)

snapshot.add(left(p));

if (right(p) != null)

snapshot.add(right(p));

return snapshot;

}

public boolean isInternal(Node p) { return numChildren(p) > 0; }

public boolean isExternal(Node p) { return numChildren(p) == 0; }

public Node left(Node p) throws IllegalArgumentException {

return p.getLeft();

}

public Node right(Node p) throws IllegalArgumentException {

return p.getRight();

}

// update methods supported by this class

/**

* Places element e at the root of an empty tree and returns its new Position.

*

* @param e the new element

* @return the Position of the new element

* @throws IllegalStateException if the tree is not empty

*/

public Node addRoot(E e) throws IllegalStateException {

if (!isEmpty()) throw new IllegalStateException("Tree is not empty");

root = new Node(e, null, null);

return root;

}

/**

* Creates a new left child of Position p storing element e and returns its Position.

*/

public Node addLeft(Node p, E e)

throws IllegalArgumentException {

if (p.getLeft() != null)

throw new IllegalArgumentException("p already has a left child");

Node child = new Node(e, null, null);

p.setLeft(child);

return child;

}

/**

* Creates a new right child of Position p storing element e and returns its Position.

*/

public Node addRight(Node p, E e)

throws IllegalArgumentException {

if (p.getRight() != null)

throw new IllegalArgumentException("p already has a right child");

Node child = new Node(e,null, null);

p.setRight(child);

return child;

}

/**

* Replaces the element at Position p with element e and returns the replaced element.

*/

public E set(Node p, E e) throws IllegalArgumentException {

E temp = p.getElement();

p.setElement(e);

return temp;

}

public void attach(Node p, simpleLinkedBinaryTree t1,

simpleLinkedBinaryTree t2) throws IllegalArgumentException {

if (isInternal(p)) throw new IllegalArgumentException("p must be a leaf");

if (!t1.isEmpty()) { // attach t1 as left subtree of node

p.setLeft(t1.root);

t1.root = null;

}

if (!t2.isEmpty()) { // attach t2 as right subtree of node

p.setRight(t2.root);

t2.root = null;

}

}

public E remove(Node p) throws IllegalArgumentException {

if (numChildren(p) == 2)

throw new IllegalArgumentException("p has two children");

Node child = (p.getLeft() != null ? p.getLeft() : p.getRight() );

if (p == root)

root = child; // child becomes root

else {

Node parent = (Node) parent(p);

if (p == parent.getLeft())

parent.setLeft(child);

else

parent.setRight(child);

}

E temp = p.getElement();

p.setElement(null); // help garbage collection

p.setLeft(null);

p.setRight(null);

return temp;

}

//pre_order traversal

private void preorderSubtree(Node p, ArrayList> snapshot) {

snapshot.add(p); // for preorder, we add position p before exploring subtrees

for (Node c : children(p))

preorderSubtree(c, snapshot);

}

public ArrayList> preorder() {

ArrayList> snapshot = new ArrayList<>();

if (!isEmpty())

preorderSubtree(root(), snapshot); // fill the snapshot recursively

return snapshot;

}

//in_order traversal

private void inorderSubtree(Node p, ArrayList> snapshot) {

if (left(p) != null)

inorderSubtree(left(p), snapshot);

snapshot.add(p);

if (right(p) != null)

inorderSubtree(right(p), snapshot);

}

public ArrayList> inorder() {

ArrayList> snapshot = new ArrayList>();

if (!isEmpty())

inorderSubtree(root(), snapshot); // fill the snapshot recursively

return snapshot;

}

//post_order traversal

private void postorderSubtree(Node p, ArrayList> snapshot) {

for (Node c : children(p))

postorderSubtree(c, snapshot);

snapshot.add(p); // for postorder, we add position p after exploring subtrees

}

public ArrayList> postorder() {

ArrayList> snapshot = new ArrayList>();

if (!isEmpty())

postorderSubtree(root(), snapshot); // fill the snapshot recursively

return snapshot;

}

/****************************************************************************************/

/*****************Your LAB starts here!******************/

/****************************************************************************************/

//Returns the number of nodes in the tree.

public int size() {

}

//Returns the Node of p's parent (or null if p is root).

public Node parent(Node p1, Node p2){

}

public boolean isIdentical(Node p1, Node p2){

}

public ArrayList> ancestors(Node p1, Node p2)

{

return null;

}

}

-------------------------------------------------------------------------------

package simpleBinaryTree;

public class Node> {

private E element; // an element stored at this node

private Node left; // a reference to the left child (if any)

private Node right; // a reference to the right child (if any)

/**

* Constructs a node with the given element and neighbors.

*

* @param e the element to be stored

* @param leftChild reference to a left child node

* @param rightChild reference to a right child node

*/

public Node(E e, Node leftChild, Node rightChild) {

element = e;

left = leftChild;

right = rightChild;

}

// accessor methods

public E getElement() { return element; }

public Node getLeft() { return left; }

public Node getRight() { return right; }

// update methods

public void setElement(E e) { element = e; }

public void setLeft(Node leftChild) { left = leftChild; }

public void setRight(Node rightChild) { right = rightChild; }

}