Question

V testANodeSimpleGetChildrenBasic V testANodeSimpleAddChildBasic V testBTreeSimpleDistanceToRootBasic V testBTreeSimplelsCloneBasic V testANodeSimplesetElementBasic V testBTreeSimpleGetHeightBasic V testAN odeSimpleGetElementBasic V testBTreeSimpleSetRootBasic V testBTreeSimpleGetRootBasic V testANodeSimplelsLeafNodeBasic V testANodeSimpleRemoveChildBasic V testBTreeSimpleReRootBasic X testDTree Advanced ReRootchangesParent

Does not pass the testcase testDTreeAdvancedReRootchangesParent

Java

I'm trying to extend the implementation of a general tree with new operations that change the structure of the tree.

I've created 5 classes: Node.java, SimpleNode.java, Tree.java, RerootableTree.java and SimpleTree.java(which is the main java class that I need to change).

The code does not pass ONE TESTCASE : testDTreeAdvancedReRootchangesParent

The code passes all the other testcases except theone mentioned above. This is because in the SimpleTree.java the method "reRoot(Node newRoot)" is most likely incorrect, this is why it doesnt run. Can you solve the public void reRoot(Node newRoot) in SimpleTree.java class

These are the 5 classes:

Node.java (Does not need change):

import java.util.List;

public interface Node {
  
   /**
   * Recovers the value stored in the node
   * @return the object stored in the node
   */
   public Object getElement();

   /**
   * Sets the value stored in the node
   * @param element the value to store in the node
   */
   public void setElement(Object element);

   /**
   * Recover the parent stored of the current node
   * @return the parent of the current node
   */
   public Node getParent();

   /**
   * Set the parent of the current node
   * @param parent to set for the current node
   */
   public void setParent(Node parent);

   /**
   * Recover a list of children in order from left to right for the node
   * @return a list of children for the node
   */
   public List getChildren();

   /**
   * Append a child node to the list of children in the order from left to right
   * @param child the new node to add to the list of children
   */  
   public void addChild(Node child);

   /**
   * Remove a child node from the list of children
   * @param child the new node to remove from the list of children
   */      
   public void removeChild(Node child);

   /**
   * Check if the node is a leaf node. A leaf node is a node which has no children
   * @return true if a leaf node else false
   */
   public boolean isLeafNode();
  
   /**
   * Check if the node is a root node. A root node is a node which does not have a parent
   * @return true if a root node else false
   */
   public boolean isRootNode();  
}

************************************************************************************************************************************************

SimpleNode.java:

import java.util.ArrayList;
import java.util.List;
////////////////////////////////////
// your code in this class 1 of 2 //
////////////////////////////////////
public class SimpleNode implements Node {
// implement 3 private classes by introducing 1. element, 2. parent and
// 3.children.
private Object element;
private Node parent;
private List children;
// implement and add all the public classes in the
// Node.java file with it's return value
// Recovers the value stored in the node
// return the object stored in the node
public Object getElement() {
return this.element;
}
// Sets the value stored in the node
// param element the value to store in the node
public void setElement(Object element) {
this.element = element;
}
// Recover the parent stored of the current node
// return the parent of the current node
public Node getParent() {
return this.parent;
}
// Set the parent of the current node
// param parent to set for the current node
public void setParent(Node parent) {
this.parent = parent;
}
// Recover a list of children in order from left to right for the node
// @return a list of children for the node
public List getChildren() {
return this.children;
}
// Append a child node to the list of children in the order from left to
// right
// @param child the new node to add to the list of children
public void addChild(Node child) {
this.children.add(child);
child.setParent(this);
}
// Remove a child node from the list of children
// @param child the new node to remove from the list of children
public void removeChild(Node child) {
this.children.remove(child);
}
// Check if the node is a leaf node. A leaf node is a node which has no
// children
// @return true if a leaf node else false
public boolean isLeafNode() {
return children.isEmpty();
}
// Check if the node is a root node. A root node is a node which does not
// have a parent
// @return true if a root node else false
public boolean isRootNode() {
return parent == null;
}
// and finally add in the last step a SimpleNode() class
public SimpleNode() {
this.parent = null;
this.children = new ArrayList();
}
}

*********************************************************************************************************************************************

Tree.java:

public interface Tree {
  
   /**
   * Calculates the size of the tree.
   * @return the number of internal and leaf nodes in the tree
   */
   public int size();

   /**
   * Checks if the tree is empty
   * @return true if the tree contains no nodes else false
   */
   public boolean isEmpty();

   /**
   * Computes the maximum height of the tree
   * @return the maximum height of the tree
   */  
   public int getHeight();
  
   /**
   * Adds a node as the root of the tree
   * @param root add a node as the root of the tree
   */
   public void setRoot(Node root);

   /**
   * Recovers the root of the tree
   * @return the root node of the tree
   */
   public Node getRoot();
  
   /**
   * Recovers the distance between the root node and the query node.
   * The distance is in terms of the number of edges between the query node
   * and the root.
    * returns a value less than zero if root or node is null
   * @param node is the initial location of the query
   * @return the distance from node to the root
   */
   public int distanceToRoot(Node node);
  
}

***************************************************************************************************************************************

SimpleTree.java:

public class SimpleTree implements RerootableTree {
// Implement a private class by introducing the root.
private Node root;
// Now
// implement and add all the public classes in the
// Tree.java file with it's return value
// Calculates the size of the tree.
// @return the number of internal and leaf nodes in the tree
public int size() {
return this.size(this.root);
}
private int size(Node root) {
// base case
if (root == null) {
return 0;
}
// recurse
int total = 1;
for (Node n : root.getChildren()) {
total += this.size(n);
}
return total;
}
/**
* Checks if the tree is empty
*
* @return true if the tree contains no nodes else false
*/
public boolean isEmpty() {
return this.root == null;
}
/**
* Computes the maximum height of the tree
*
* @return the maximum height of the tree
*/
// gets the height from the private method of get height.
public int getHeight() {
return this.getHeight(root);
}// Computes the maximum height of the tree
private int getHeight(Node root) {
int h = 0;
// Base case: If tree is empty then height is -1.
if (root == null) {
return -1;
}
// Recurse through and add 1 every time method has to recurse again
else {
for (Node n : root.getChildren()) {
h = Math.max(h, 1 + getHeight(n));
}
}
return h;
}
/**
* Adds a node as the root of the tree
*
* @param root
* add a node as the root of the tree
*/
public void setRoot(Node root) {
this.root = root;
}
/**
* Recovers the root of the tree
*
* @return the root node of the tree
*/
public Node getRoot() {
return this.root;
}
/**
* Recovers the distance between the root node and the query node. The
* distance is in terms of the number of edges between the query node and
* the root. returns a value less than zero if root or node is null
*
* @param node
* is the initial location of the query
* @return the distance from node to the root
*/
public int distanceToRoot(Node node) {
// Base case
if (node == getRoot())
return 0;
// We recurse through the tree add 1 every time method has to recurse
// again
else
return 1 + distanceToRoot(node.getParent());
}
// Now implementing the classes from RerootableTree.java
/**
* Sets a new root node for the current tree. To see how this operation
* works check the assignment specifications
*
* @param newRoot
* the node which will be updated as the root for the current
* tree
*/
public void reRoot(Node newRoot) {
  
// Check if newRoot has a parent and has been added to the tree or its just isolated node
if(newRoot.getParent()!=null)
{
Node parentOfNewRoot = newRoot.getParent();
// Base case: While the tree is empty or the root already equals new
// root then exit the method
if (isEmpty() == true || this.getRoot().equals(newRoot)) {
return;
} else {
// We recurse through the tree
this.reRoot(parentOfNewRoot);
// Setting the root to the root entered as parameter as this will be
// the new root
this.setRoot(newRoot);
// Make sure that new root is not a child anymore of the parents it
// had previously, by removing it
parentOfNewRoot.removeChild(newRoot);
// The parents of the new root will now become its children
newRoot.addChild(parentOfNewRoot);
}
}
}
/**
* Checks if the current tree is a clone of "tree". For more details see
* assignment specifications
*
* @param tree
* @return true if the tree is a clone otherwise false
*/
public boolean isClone(Tree tree) {
// While both tree are empty we return true as they will be equal
if (tree.isEmpty() == true && this.isEmpty() == true) {
return true;
}
// If the size of both tree is not equal then they cannot be equal
if (!(this.size() == tree.size())) {
return false;
}
// If the root of both tree is not equal then they cannot be equal
if (!(this.getRoot() == tree.getRoot())) {
return false;
}
// If the number of children of both tree is not equal then they cannot
// be equal
if (this.getRoot().getChildren().size() != tree.getRoot().getChildren().size()) {
return false;
}
// We create two new trees
SimpleTree a = new SimpleTree();
SimpleTree b = new SimpleTree();
// If the tree pass all the above conditions then we iterate through the
// tree checking each node
for (int i = 0; i < a.size(); i++) {
Node a1 = a.getRoot().getChildren().get(i);
Node b1 = b.getRoot().getChildren().get(i);
a.setRoot(a1);
b.setRoot(b1);
// Comparing the tree by setting each child as the root node. If
// trees are not equal return false.
if (a.isClone(b) == false)
return false;
}
// If both trees are not empty and all conditions fail the return true
// as this means both tree are equal
return true;
}
// Finally implement the whole data
public SimpleTree() {
this.root = null;
}

  
}

************************************************************************************************************************************************

RerootableTree.java:

public interface RerootableTree extends Tree {
  
   /**
   * Sets a new root node for the current tree. To see how this operation works
   * check the assignment specifications
   * @param newRoot the node which will be updated as the root for the current tree
   */
   public void reRoot(Node newRoot) ;

   /**
   * Checks if the current tree is a clone of "tree". For more details see assignment specifications
   * @param tree
   * @return true if the tree is a clone otherwise false
   */
   public boolean isClone(Tree tree) ;
}

Answer 1

PROGRAM CODE:

RerootableTree.java

public interface RerootableTree extends Tree {
  
   /**
   * Sets a new root node for the current tree. To see how this operation works
   * check the assignment specifications
   * @param newRoot the node which will be updated as the root for the current tree
   */
   public Node reRoot(Node newRoot) ;
   /**
   * Checks if the current tree is a clone of "tree". For more details see assignment specifications
   * @param tree
   * @return true if the tree is a clone otherwise false
   */
   public boolean isClone(Tree tree) ;
   }

SimpleTree.java

import java.util.List;

public class SimpleTree implements RerootableTree {
   // Implement a private class by introducing the root.
   private Node root;
   // Now
   // implement and add all the public classes in the
   // Tree.java file with it's return value
   // Calculates the size of the tree.
   // @return the number of internal and leaf nodes in the tree
   public int size() {
   return this.size(this.root);
   }
   private int size(Node root) {
   // base case
   if (root == null) {
   return 0;
   }
   // recurse
   int total = 1;
  
   for (Node n : root.getChildren()) {
   total += this.size(n);
   }
   return total;
   }
   /**
   * Checks if the tree is empty
   *
   * @return true if the tree contains no nodes else false
   */
   public boolean isEmpty() {
   return this.root == null;
   }
   /**
   * Computes the maximum height of the tree
   *
   * @return the maximum height of the tree
   */
   // gets the height from the private method of get height.
   public int getHeight() {
   return this.getHeight(root);
   }// Computes the maximum height of the tree
   private int getHeight(Node root) {
   int h = 0;
   // Base case: If tree is empty then height is -1.
   if (root == null) {
   return -1;
   }
   // Recurse through and add 1 every time method has to recurse again
   else {
       List<Node> nodes = root.getChildren();
   for (Node n : nodes) {
   h = Math.max(h, 1 + getHeight(n));
   }
   }
   return h;
   }
   /**
   * Adds a node as the root of the tree
   *
   * @param root
   * add a node as the root of the tree
   */
   public void setRoot(Node root) {
   this.root = root;
   }
   /**
   * Recovers the root of the tree
   *
   * @return the root node of the tree
   */
   public Node getRoot() {
   return this.root;
   }
   /**
   * Recovers the distance between the root node and the query node. The
   * distance is in terms of the number of edges between the query node and
   * the root. returns a value less than zero if root or node is null
   *
   * @param node
   * is the initial location of the query
   * @return the distance from node to the root
   */
   public int distanceToRoot(Node node) {
   // Base case
   if (node == getRoot())
   return 0;
   // We recurse through the tree add 1 every time method has to recurse
   // again
   else
   return 1 + distanceToRoot(node.getParent());
   }
   // Now implementing the classes from RerootableTree.java
   /**
   * Sets a new root node for the current tree. To see how this operation
   * works check the assignment specifications
   *
   * @param newRoot
   * the node which will be updated as the root for the current
   * tree
   */
   public Node reRoot(Node newRoot) {
  
   // Check if newRoot has a parent and has been added to the tree or its just isolated node
   if(newRoot.getParent()!=null)
   {
   Node parentOfNewRoot = newRoot.getParent();
   // Base case: While the tree is empty or the root already equals new
   // root then exit the method
   if (isEmpty() == true || this.getRoot().equals(newRoot)) {
   return newRoot;
   } else {
   // We recurse through the tree
   this.reRoot(parentOfNewRoot);
   // Setting the root to the root entered as parameter as this will be
   // the new root
   this.setRoot(newRoot);
   // Make sure that new root is not a child anymore of the parents it
   // had previously, by removing it
   parentOfNewRoot.removeChild(newRoot);
   // The parents of the new root will now become its children
   newRoot.addChild(parentOfNewRoot);
   }
   }
   return newRoot;
   }
   /**
   * Checks if the current tree is a clone of "tree". For more details see
   * assignment specifications
   *
   * @param tree
   * @return true if the tree is a clone otherwise false
   */
   public boolean isClone(Tree tree) {
   // While both tree are empty we return true as they will be equal
   if (tree.isEmpty() == true && this.isEmpty() == true) {
   return true;
   }
   // If the size of both tree is not equal then they cannot be equal
   if (!(this.size() == tree.size())) {
   return false;
   }
   // If the root of both tree is not equal then they cannot be equal
   if (!(this.getRoot() == tree.getRoot())) {
   return false;
   }
   // If the number of children of both tree is not equal then they cannot
   // be equal
   if (this.getRoot().getChildren().size() != tree.getRoot().getChildren().size()) {
   return false;
   }
   // We create two new trees
   SimpleTree a = new SimpleTree();
   SimpleTree b = new SimpleTree();
   // If the tree pass all the above conditions then we iterate through the
   // tree checking each node
   for (int i = 0; i < a.size(); i++) {
   Node a1 = a.getRoot().getChildren().get(i);
   Node b1 = b.getRoot().getChildren().get(i);
   a.setRoot(a1);
   b.setRoot(b1);
   // Comparing the tree by setting each child as the root node. If
   // trees are not equal return false.
   if (a.isClone(b) == false)
   return false;
   }
   // If both trees are not empty and all conditions fail the return true
   // as this means both tree are equal
   return true;
   }
   // Finally implement the whole data
   public SimpleTree() {
   this.root = null;
   }
  
   }

//Main class created by me to test

MainClass.java

public class MainClass {

   /**
   * @param args
   */
   public static void main(String[] args) {
       Node node = new SimpleNode();
       Node node1 = new SimpleNode();
       node.setElement("Child");
       node1.setElement("Parent");
       node.addChild(node1);
       SimpleTree tree = new SimpleTree();
       tree.setRoot(node);
       System.out.println(tree.getRoot().getElement());
       tree.setRoot(tree.reRoot(node1));
       System.out.println(tree.getRoot().getElement());
       System.out.println(tree.size());
   }

}

OUTPUT:

Child //output before rerooting
Parent //output after rerooting
2