Code:

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

2. 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 a) public int size) //return the number of nodes b) public Node parent(NodeEp) throws IllegalArgumentException //return the parent node for a node referred by 3. Add and implement the following methods within the class: c) public boolean isldentical(Nodepi, NodeE> p2): check if two binary trees rooted at pl 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 http://www.techiedelight.com/check-if-two-binary-trees-are-identical-not-iterative- recursive/ d) public ArrayList NodeE>> ancestors(Nodepl, NodeE> p2): find all ancestors of a given node referred by p2 on a tree rooted at pl http://www.techiedelight.com/find-ancestors-of-given-node-binary-tree/