Write and test a copy constructor for the Binary Search Tree class. A copy constructor takes a reference to a BST and creates a copy. Note that you cannot just copy the root reference. You must go through the original tree and create copies of all the nodes. This is easiest to do with a recursive function that takes a parameter that is a Node. If the Node is null, return null, else return a new node that contains as data a copy of the original Node object,data, and the left and right references refer to copies of the left and right subtrees of the original Node. These copies are returned by recursive calls to the copy function. This is called making a deep copy. Test the constructor by creating a tree, making a copy of it, and then modifying the copy. Print out both the original tree and the copy to show they are actually different trees.

//==================================================== public class BinarySearchTree2 { private Node root; public BinarySearchTree2(){ this.root = null; } //==================================================== public boolean find(int id){ Node current = root; while(current!=null){ if(current.data==id){ return true; }else if(current.data>id){ current = current.left; }else{ current = current.right; } } return false; } //==================================================== public boolean delete(int id){ Node parent = root; Node current = root; boolean isLeftChild = false; while(current.data!=id){ parent = current; if(current.data>id){ isLeftChild = true; current = current.left; }else{ isLeftChild = false; current = current.right; } if(current ==null){ return false; } } //if i am here that means we have found the node //Case 1: if node to be deleted has no children if(current.left==null && current.right==null){ if(current==root){ root = null; } if(isLeftChild ==true){ parent.left = null; }else{ parent.right = null; } } //Case 2 : if node to be deleted has only one child else if(current.right==null){ if(current==root){ root = current.left; }else if(isLeftChild){ parent.left = current.left; }else{ parent.right = current.left; } } else if(current.left==null){ if(current==root){ root = current.right; }else if(isLeftChild){ parent.left = current.right; }else{ parent.right = current.right; } }else if(current.left!=null && current.right!=null){ //now we have found the minimum element in the right sub tree Node successor = getSuccessor(current); if(current==root){ root = successor; }else if(isLeftChild){ parent.left = successor; }else{ parent.right = successor; } successor.left = current.left; } return true; } //==================================================== public Node getSuccessor(Node deleleNode){ Node successsor =null; Node successsorParent =null; Node current = deleleNode.right; while(current!=null){ successsorParent = successsor; successsor = current; current = current.left; } //check if successor has the right child, it cannot have left child for sure // if it does have the right child, add it to the left of successorParent. // successsorParent if(successsor!=deleleNode.right){ successsorParent.left = successsor.right; successsor.right = deleleNode.right; } return successsor; } //==================================================== public void insert(int id){ Node newNode = new Node(id); if(root==null){ root = newNode; return; } Node current = root; Node parent = null; while(true){ parent = current; if(id rDepth) return (lDepth + 1); else return (rDepth + 1); } } public int size() { return(size(root)); } private int size(Node node) { if (node == null) return(0); else { return(size(node.left) + 1 + size(node.right)); } } //==================================================== public static void main(String arg[]){ BinarySearchTree2 b = new BinarySearchTree2(); b.insert(3);b.insert(8); b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9); b.insert(20);b.insert(25);b.insert(15);b.insert(16); System.out.println("Original Tree : "); b.display(); System.out.println(""); System.out.println("Check whether Node with value 4 exists : " + b.find(4)); System.out.println("Delete Node with no children (2) : " + b.delete(2)); b.display(); System.out.println(" Delete Node with one child (4) : " + b.delete(4)); b.display(); System.out.println(" Delete Node with Two children (10) : " + b.delete(10)); b.display(); System.out.println(); System.out.println(" The depth of the tree is: " + b.getDepth()); System.out.println(" The size of the tree is: " + b.size()); } } //==================================================== class Node{ int data; Node left; Node right; public Node(int data){ this.data = data; left = null; right = null; } }