Question

complete java binary search tree

/*
* Complete the printInLevelOrder() method
* Complete the visuallyIdentical(A4BST rhs) method
* No other methods/variables should be added/modified
*/
public class A4BST<E extends Comparable<? super E>> {
   /*
   * Grading:
   * Correctly prints values in level order - 1.5pt
   * Runs in O(N) - 1.5pt
   */
   public String printInLevelOrder()
   {
       String content = "";
       /*
       * Add items from the tree to content one level at a time
       * No line breaks are required between levels
       * Ensure method runs in O(N) - does not revisit any node
       */
       return content;
   }
   /*
   * Grading:
   * Correctly compares the structure of both trees - 3pts
   */
   public boolean visuallyIdentical(A4BST rhs)
   {
       /*
       * Check if the structure of the local tree and the rhs tree are identical
       * This means they have the same left/right connections
       * This means there are no extra connections in either tree
       * The values at each position do not need to match, only the structure of the tree
       * Think about if you drew both trees on paper, would they visually look the same (besides values)
       */
       return false;
   }
  
   private Node root;

   public A4BST()
   {
       root = null;
   }

   public String printTree()
   {
       return printTree(root);
   }
   private String printTree(Node current)
   {
       String content = "";
       if(current != null)
       {
           content += "Current:"+current.data.toString();
           if(current.left != null)
           {
               content += "; Left side:"+current.left.data.toString();
           }
           if(current.right != null)
           {
               content += "; Right side:"+current.right.data.toString();
           }
           content+="\n";
           content+=printTree(current.left);
           content+=printTree(current.right);

       }
       return content;
   }
   public String printInOrder()
   {
       return printInOrder(root);
   }
   private String printInOrder(Node current)
   {
       String content = "";
       if(current != null)
       {
           content += printInOrder(current.left);
           content += current.data.toString()+",";
           content += printInOrder(current.right);
       }
       return content;
   }
   public boolean contains(E val)
   {
       Node result = findNode(val, root);

       if(result != null)
           return true;
       else
           return false;
   }
   private Node findNode(E val, Node current)
   {
       //base cases
       if(current == null)
           return null;
       if(current.data.equals(val))
           return current;

       //recursive cases
       int result = current.data.compareTo(val);
       if(result < 0)
           return findNode(val, current.right);
       else
           return findNode(val, current.left);
   }
   public E findMin()
   {
       Node result = findMin(root);
       if(result == null)
           return null;
       else
           return result.data;
   }
   private Node findMin(Node current)//used in findMin and delete
   {
       while(current.left != null)
       {
           current = current.left;
       }
       return current;
   }
   public E findMax()
   {
       Node current = root;
       while(current.right != null)
       {
           current = current.right;
       }
       return current.data;
   }
   public void insert(E val)
   {
       root = insertHelper(val, root);
   }
   public Node insertHelper(E val, Node current)
   {
       if(current == null)
       {
           return new Node(val);
       }
       int result = current.data.compareTo(val);
       if(result < 0)
       {
           current.right = insertHelper(val, current.right);
       }
       else if(result > 0)
       {
           current.left = insertHelper(val, current.left);
       }
       else//update
       {
           current.data = val;
       }
       return current;
   }
   public void remove(E val)
   {
       root = removeHelper(val, root);
   }
   private Node removeHelper(E val, Node current)
   {
       if(current.data.equals(val))
       {
           if(current.left == null && current.right == null)//no children
           {
               return null;
           }
           else if(current.left != null && current.right != null)//two children
           {
               Node result = findMin(current.right);
               result.right = removeHelper(result.data, current.right);
               result.left = current.left;
               return result;
           }
           else//one child
           {
               return (current.left != null)? current.left : current.right;
           }
       }
       int result = current.data.compareTo(val);
       if(result < 0)
       {
           current.right = removeHelper(val, current.right);
       }
       else if(result > 0)
       {
           current.left = removeHelper(val, current.left);
       }
       return current;
   }

   private class Node
   {
       E data;
       Node left, right;
       public Node(E d)
       {
           data = d;
           left = null;
           right = null;
       }
   }

}

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

public class A4Driver {

   public static void main(String[] args) {
       A4BST<Integer> tree1 = new A4BST<>();
       tree1.insert(5);
       tree1.insert(3);
       tree1.insert(1);
       tree1.insert(2);
       tree1.insert(9);
       tree1.insert(10);
       tree1.insert(25);
       A4BST<Integer> tree2 = new A4BST<>();
       tree2.insert(8);
       tree2.insert(5);
       tree2.insert(1);
       tree2.insert(3);
       tree2.insert(15);
       tree2.insert(20);
       tree2.insert(25);
       A4BST<Integer> tree3 = new A4BST<>();
       tree3.insert(1);
       tree3.insert(2);
       tree3.insert(3);
       tree3.insert(5);
       tree3.insert(9);
       tree3.insert(10);
       tree3.insert(25);
       System.out.println(tree1.printInLevelOrder());//5, 3, 9, 1, 10, 2, 25
       System.out.println(tree2.printInLevelOrder());//8, 5, 15, 1, 20, 3, 25
       System.out.println(tree3.printInLevelOrder());//1, 2, 3, 4, 5, 9, 10, 25
       System.out.println(tree1.visuallyIdentical(tree2));//true
       System.out.println(tree1.visuallyIdentical(tree3));//false
  
  

   }

}

Answer 1

/* A4BST.java */
import java.util.LinkedList;
import java.util.Queue;

public class A4BST<E extends Comparable<? super E>> {
/*
* Grading:
* Correctly prints values in level order - 1.5pt
* Runs in O(N) - 1.5pt
*/
public String printInLevelOrder()
{
String content = "";
/*
* Add items from the tree to content one level at a time
* No line breaks are required between levels
* Ensure method runs in O(N) - does not revisit any node
*/
// Base Case
if(root == null)
return content;
  
// Create an empty queue for level order tarversal
Queue<Node> q =new LinkedList<Node>();
  
// Enqueue Root and initialize height
q.add(root);
  
  
while(true)
{
  
// nodeCount (queue size) indicates number of nodes
// at current level.
int nodeCount = q.size();
if(nodeCount == 0)
break;
  
// Dequeue all nodes of current level and Enqueue all
// nodes of next level
while(nodeCount > 0)
{
Node node = q.peek();
content= content + node.data + " ";
q.remove();
if(node.left != null)
q.add(node.left);
if(node.right != null)
q.add(node.right);
nodeCount--;
}
  
}
return content;
}
/*
* Grading:
* Correctly compares the structure of both trees - 3pts
*/

public boolean visuallyIdentical(A4BST rhs)
{
/*
* Check if the structure of the local tree and the rhs tree are identical
* This means they have the same left/right connections
* This means there are no extra connections in either tree
* The values at each position do not need to match, only the structure of the tree
* Think about if you drew both trees on paper, would they visually look the same (besides values)
*/
// Return true if both trees are empty
if (this.root == null && rhs.root == null) return true;

// Return false if one is empty and other is not
if (this.root == null || rhs.root == null) return false;

// Create an empty queues for simultaneous traversals
Queue<Node > q1 = new LinkedList<Node> ();
Queue<Node> q2 = new LinkedList<Node> ();

// Enqueue Roots of trees in respective queues
q1.add(this.root);
q2.add(rhs.root);

while (!q1.isEmpty() && !q2.isEmpty())
{
// Get front nodes and compare them
Node n1 = q1.peek();
Node n2 = q2.peek();
// Remove front nodes from queues
q1.remove();
q2.remove();

/* Enqueue left children of both nodes */
if (n1.left != null && n2.left != null)
{
q1.add(n1.left);
q2.add(n2.left);
}

// If one left child is empty and other is not
else if (n1.left != null || n2.left != null)
return false;

// Right child code (Similar to left child code)
if (n1.right != null && n2.right != null)
{
q1.add(n1.right);
q2.add(n2.right);
}
else if (n1.right != null || n2.right != null)
return false;
}

return true;

}
  
private Node root;

public A4BST()
{
root = null;
}

public String printTree()
{
return printTree(root);
}
private String printTree(Node current)
{
String content = "";
if(current != null)
{
content += "Current:"+current.data.toString();
if(current.left != null)
{
content += "; Left side:"+current.left.data.toString();
}
if(current.right != null)
{
content += "; Right side:"+current.right.data.toString();
}
content+="\n";
content+=printTree(current.left);
content+=printTree(current.right);

}
return content;
}
public String printInOrder()
{
return printInOrder(root);
}
private String printInOrder(Node current)
{
String content = "";
if(current != null)
{
content += printInOrder(current.left);
content += current.data.toString()+",";
content += printInOrder(current.right);
}
return content;
}
public boolean contains(E val)
{
Node result = findNode(val, root);

if(result != null)
return true;
else
return false;
}
private Node findNode(E val, Node current)
{
//base cases
if(current == null)
return null;
if(current.data.equals(val))
return current;

//recursive cases
int result = current.data.compareTo(val);
if(result < 0)
return findNode(val, current.right);
else
return findNode(val, current.left);
}
public E findMin()
{
Node result = findMin(root);
if(result == null)
return null;
else
return result.data;
}
private Node findMin(Node current)//used in findMin and delete
{
while(current.left != null)
{
current = current.left;
}
return current;
}
public E findMax()
{
Node current = root;
while(current.right != null)
{
current = current.right;
}
return current.data;
}
public void insert(E val)
{
root = insertHelper(val, root);
}
public Node insertHelper(E val, Node current)
{
if(current == null)
{
return new Node(val);
}
int result = current.data.compareTo(val);
if(result < 0)
{
current.right = insertHelper(val, current.right);
}
else if(result > 0)
{
current.left = insertHelper(val, current.left);
}
else//update
{
current.data = val;
}
return current;
}
public void remove(E val)
{
root = removeHelper(val, root);
}
private Node removeHelper(E val, Node current)
{
if(current.data.equals(val))
{
if(current.left == null && current.right == null)//no children
{
return null;
}
else if(current.left != null && current.right != null)//two children
{
Node result = findMin(current.right);
result.right = removeHelper(result.data, current.right);
result.left = current.left;
return result;
}
else//one child
{
return (current.left != null)? current.left : current.right;
}
}
int result = current.data.compareTo(val);
if(result < 0)
{
current.right = removeHelper(val, current.right);
}
else if(result > 0)
{
current.left = removeHelper(val, current.left);
}
return current;
}
private class Node
{
E data;
Node left, right;
public Node(E d)
{
data = d;
left = null;
right = null;
}
}
}

/* A4Driver.java */

public class A4Driver {

public static void main(String[] args) {
A4BST<Integer> tree1 = new A4BST<>();
tree1.insert(5);
tree1.insert(3);
tree1.insert(1);
tree1.insert(2);
tree1.insert(9);
tree1.insert(10);
tree1.insert(25);
A4BST<Integer> tree2 = new A4BST<>();
tree2.insert(8);
tree2.insert(5);
tree2.insert(1);
tree2.insert(3);
tree2.insert(15);
tree2.insert(20);
tree2.insert(25);
A4BST<Integer> tree3 = new A4BST<>();
tree3.insert(1);
tree3.insert(2);
tree3.insert(3);
tree3.insert(5);
tree3.insert(9);
tree3.insert(10);
tree3.insert(25);
System.out.println(tree1.printInLevelOrder());//5, 3, 9, 1, 10, 2, 25
System.out.println(tree2.printInLevelOrder());//8, 5, 15, 1, 20, 3, 25
System.out.println(tree3.printInLevelOrder());//1, 2, 3, 4, 5, 9, 10, 25
System.out.println(tree1.visuallyIdentical(tree2));//true
System.out.println(tree1.visuallyIdentical(tree3));//false

}

}

/* OUTPUT */

/* PLEASE UPVOTE */