Please provide following for code given(Duplicate the given Tree)

Purpose: explain what your implementation is expected to achieve. Include the header of your method in java syntax. For illustrating this step you will include Input, Process and Output in tabular form.

Methods Name datatype name(parameters)

Use/Purpose What does your method do

Inputs Description of the parameters taken

Outputs Return value. e.g false if element not found, true otherwise.

Pre-condition What do you need to have for your method to work

Pos-condition What is the status of you data structures when finished execution

import java.util.Scanner;

public class Main{

public static void main(String[] args) {

BSTree arbol1= new BSTree(); //create first tree arbol1.inorder(); //traverse the first tree (empty)

arbol1.insert(50); //insert first value arbol1.insert(50); //try to add duplicate arbol1.inorder();

arbol1.insert(55); arbol1.insert(40); arbol1.inorder(); System.out.println(" Size of arbol1 is: "+arbol1.getSize()+ " nodes"); BSTree arbol2= new BSTree(new int[] {10,20,15,45,62,99,36}); System.out.println(" Size of arbol2 is: "+arbol2.getSize()+ " nodes");

arbol2.inorder(); arbol2.preorder(); arbol2.posorder(); //creating duplicate tree for arbol1 BSTree duplicate1 = new BSTree(); duplicate1.duplicateTree(arbol1);//calling duplicateTree method System.out.println(" Size of duplicate tree of arbol1 is: "+duplicate1.getSize()+ " nodes"); duplicate1.inorder(); duplicate1.preorder(); duplicate1.posorder();

//creating duplicate tree for arbol2 BSTree duplicate2 = new BSTree(); duplicate2.duplicateTree(arbol2);//calling duplicateTree method System.out.println(" Size of duplicate tree of arbol2 is: "+duplicate2.getSize()+ " nodes"); duplicate2.inorder(); duplicate2.preorder(); duplicate2.posorder();

} }

class BSTree { private TreeNode root; //Create a reference that will point to the root node private int size=0; //Number of nodes in the tree public BSTree() { //Default constructor } public BSTree(int[] args) { //Use the insertion method to create a tree from an array for(int i=0;i

this.insert(args[i]); TreeNode duproot = clone(root); } public boolean isEmpty() { if (size==0) return true; else return false; } public int getSize() { return size; } public static TreeNode clone (TreeNode root) {if(root==null){return null;} TreeNode temp= new TreeNode(root.data); temp.left=clone(root.left); temp.right=clone(root.right); return temp; } //The following insertion method adds a node to the tree if the value is not already in public boolean insert(int value) { if(root == null) { //The tree is empty, make the new node root root = new TreeNode(value); } else { TreeNode node = root; TreeNode parent = null; while(node != null) { //This while searched the location of the new node if(value < node.data) { parent = node; node = node.left; } else if(value > node.data){ parent = node; node = node.right; } else { System.out.println(" The value already exists in the tree and cannot be added"); return false; //Exit with false, the node was not added } } node = new TreeNode(value); //create the new node if(value < parent.data) parent.left=node; //add the node on the correct subtree else parent.right=node; } size++; //You have added one more node return true; //The node was successfully added } public void inorder() { //This is a helper method needed to invoke inorder with parameters System.out.print(" Tree InOrder -> [ "); inorder(root); System.out.print("]"); } protected void inorder(TreeNode root) { //inorder with parameters allows a recursion if (root == null) return; inorder(root.left); System.out.print(root.data + " "); inorder(root.right); } public void preorder() { //This is a helper method needed to invoke preorder with parameters System.out.print(" Tree PreOrder -> [ "); preorder(root); System.out.print("]"); } protected void preorder(TreeNode root) { //preorder with parameters allows a recursion if (root == null) return; System.out.print(root.data + " "); preorder(root.left); preorder(root.right); } public void posorder() { //This is a helper method needed to invoke posorder with parameters System.out.print(" Tree PosOrder -> [ "); posorder(root); System.out.print("]"); } protected void posorder(TreeNode root) { //posorder with parameters allows a recursion if (root == null) return; posorder(root.left); posorder(root.right); System.out.print(root.data + " "); } public boolean search(int value) { if (root==null) return false; TreeNode node = root; while(node!=null){ if(value < node.data) node = node.left; else if(value > node.data) node = node.right; else return true; } return false; } //Helper method for calling the recursive search public boolean RecSearch(int value) { return RecSearch(root,value); } protected boolean RecSearch(TreeNode root, int value) { if (root==null) //The tree is empty return false; if (root.data==value) //Element is found return true; else //Recursive search on both left and right subtrees return (RecSearch(root.left,value)||RecSearch(root.right,value)); } public boolean remove(int value) { if(root == null) { //The tree is empty, exit routine with false return false; } else { TreeNode node = root; TreeNode parent = null; while(node != null) { //This while loop searches the element if(value < node.data) { parent = node; node = node.left; } else if(value > node.data){ parent = node; node = node.right; } else { break; //element found, stop the search } } if(node==null) return false; //element not found, exit with false else { //Removing the element after it was located if(node.right==null && node.left==null) { //element is a leaf if(parent==null) { //the tree has only a root node root=null; } else if(parent.left==node) parent.left=null; else parent.right=null; } else { // the element has children if(node.right==null) { //element has only a left tree if(parent==null) //the tree has only a root node root=node.left; else if(parent.left==node) parent.left=node.left; else parent.right=node.left; } else { if(node.left==null) { //element has only a right tree if(parent==null) //the tree has only a root node root=node.right; else if(parent.right==node) parent.right=node.right; else parent.right=node.left; } else { //the element has both children TreeNode aux=parent=node; node=node.left; while(node.right!=null) { parent=node; node=node.right; } aux.data=node.data; if(parent==aux) { parent.left=null; } else parent.right=null; } } } size--; return true; //node has been removed } } } //method to create duplicate Tree for given tree // by inserting the nodes in the level order public void duplicateTree(BSTree original){ int h = height(original.root);//calculating height of the given tree int i; // for every height we insert that level nodes by calling insertGivenLevelNodes for (i=1; i<=h; i++) insertGivenLevelNodes(original.root, i); } //method to calculate height of the tree int height(TreeNode root) { if (root == null) return 0; else { /* compute height of each subtree */ int lheight = height(root.left); int rheight = height(root.right); /* use the larger one */ if (lheight > rheight) return(lheight+1); else return(rheight+1); } } //method to insert nodes for the given level void insertGivenLevelNodes (TreeNode root ,int level) { if (root == null) return; if (level == 1){ this.insert(root.data); } else if (level > 1) { insertGivenLevelNodes(root.left, level-1); insertGivenLevelNodes(root.right, level-1); } }

}

class TreeNode { public int data; public TreeNode left; public TreeNode right; public TreeNode(int nbr) { this.data = nbr; this.left = null; this.right = null; } }