Download, compile and run the sample program. Add a recursive method named getDe

Question

Download, compile and run the sample program. Add a recursive method named getDepth() that returns an int that is the depth of the deepest node in the tree. Also add a recursive method named getSize() that returns the number of nodes in the tree. Add code to the main program to test your methods.

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.

Code:

Explanation / Answer

I have implemented getDepth(), getSize() and copy() functions. I have shown their working in the main file.

Below is the running code:

//====================================================
public class BinarySearchTree2 {
private Node root;
public BinarySearchTree2(){
this.root = null;
}
//====================================================
public BinarySearchTree2 copy(){
      
        Node root = this.root;
        BinarySearchTree2 copy_tree = new BinarySearchTree2();

        copy_tree.root = copy_node(root);
        return copy_tree;
}
public Node copy_node(Node node) {
        if(node==null){
          return null;
        }
        Node left = null;
        Node right = null;
        if (node.left != null) {
            left = copy_node(node.left);
        }
        if (node.right != null) {
            right = copy_node(node.right);
        }
        Node n = new Node(node.data);
        n.left = left;
        n.right = right;
        return n;
    }

//====================================================

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<current.data){  
    current = current.left;
    if(current==null){
     parent.left = newNode;
     return;
    }
   }else{
    current = current.right;
    if(current==null){
     parent.right = newNode;
     return;
    }
   }
}
}
//====================================================
private void display(Node root){
if(root!=null){
   display(root.left);
   System.out.print(" " + root.data);
   display(root.right);
}
}
public void display(){
   display(root);
}
//====================================================

public int getDepth(Node node){
   if (node == null)
            return 0;
        else
        {
            /* compute the depth of each subtree */
            int lDepth = getDepth(node.left);
            int rDepth = getDepth(node.right);

            /* use the larger one */
            if (lDepth > rDepth)
                return (lDepth + 1);
             else
                return (rDepth + 1);
        }
}

//====================================================
public int getSize(Node node){
Node right = node.right;
Node left = node.left;
int c = 1;                                      // count yourself!
if ( right != null ) c += getSize(right);        // count sub trees
if ( left != null ) c += getSize(left);          // ..
return c;
// return a;
}

//====================================================
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();

//Get the head of the binary search tree
Node head = b.root;

//Print its depth
System.out.println(" Depth of Tree : " + b.getDepth(head));

//Print its size
System.out.println(" Size of Tree : " + b.getSize(head));

//Display the tree
System.out.println("Tree b:");
b.display();

//Create copy of b
System.out.println(" Creating a copy of b");
BinarySearchTree2 b_copy = b.copy();
System.out.println(" B_Copy:");
b_copy.display();
System.out.println(" Deleting node 1:"+b_copy.delete(1));
System.out.println(" displaying b:");
b.display();
System.out.println(" displaying b_copy:");
b_copy.display();
System.out.println();
}
}
//====================================================
class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
left = null;
right = null;
}
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.