Binary Search Tree Cloning - Java

Question

It's a homework problem. we need to build a method in java that clones a given binary search tree through recursion, ive looked up several examples online, the problem being that the program our instructor asked us to write was in what he called the Modern method, whereby rather than checking for null in each method, a tree is constructed using Dynamic dispatch from an Interface Node, connected to two subclasses nil(representing an empty node and the necessary methods to deal with an instance of an empty Node) and Vertex, a filled node and its affiliate methods. im confused on how to structure the recursion to clone the nodes, and construct the nodes to hold the cloned info. this being homework im obviously not looking for an answer but i really need some help with this.

 interface Node<T extends Comparable<T>>
{
    public int size();//return the number of values in the tree
    public boolean empty();//true if tree is empty nil
    public Node<T> insert(T x);// insert something into a binary search tree, return the node it was inserted into
    public vertex<T> search(T x);//search for a given value and return the vertex ( filled node ) it exists in
    public int depth();//returns the greatest depth of the tree
    public void inorder();
    //public Node<T> Attack_of_the_clones();
}
//note that insert must be used as in t = t.insert(x)


class nil<T extends Comparable<T>> implements Node<T> //empty tree
{
    public int size() {return 0;}// empty node, therefore of size zero
    public boolean empty() { return true; }//its and empty node, duh
    public Node<T> insert(T x) { return new vertex<T>(x); }// returns a Tpe Node for inserting a given value into a node (thereby creating a 
                                                              //vertex containing said inserted value)
    public vertex<T> search (T x) { return null; }//RETURNS NULL IN SEARCHING FOR A GIVE VALUE BECAUSE NODES OF TPE nIL ARE INHERENTLY empty
    public int depth() { return 0; }
    public void inorder() { System.out.print("0");}
    //public Node<T> Attack_of_the_clones() { return new nil<T>(this); }
}//end nil

class vertex<T extends Comparable<T>> implements Node<T>
{
    protected T head;// the root of the tree
    protected Node<T> left;//creates an instance of Node to serve as the left child of head
    protected Node<T> right;

    //constructor
    public vertex(T h, Node<T> l, Node<T> r) { head = h; left = l; right = r; }// a constructed instance
    //leaf instructor
    public vertex(T h) { head = h; left = new nil<T>(); right = new nil<T>(); }//a constructed leaf
    // a leaf is Tpically a node with no or null children, some consider the null nodes themselves to be leaves

    //accesors so that the protected variables can be displayed
    public T acHead() {return head;}
    public Node<T> acLeft() {return left;}
    public Node<T> acRight() {return right;}

    public int size()
    {
        return left.size() + right.size() + 1;//recursively call size down the left and right trees to get all the nodes,
                                              // and combine them ( +1 for the root) to get the size of the tree
    }

    public int depth()
    {
        return Math.max((left.depth()+1),(right.depth()+1));
    }

    public boolean empty() {return false; }//because its of class vertex and therefore not empty

    public Node<T> insert(T x)
    {
        if (x.compareTo(head) <= 0)// go down left tree
            left = left.insert(x);
        else right = right.insert(x);// go right
        return this;//root vertex has not changed
    }//end insert

    public vertex<T> search(T x)
    {
        int r = x.compareTo(head);
        if(r==0)//go left
        {
            return left.search(x);//recursively call search using said node to move down tree
        }
        else //go right
        {
            return right.search(x);
        }
    }// end binary search
    public void inorder()
    {
        Node<T> current_root = this;
        if(current_root == null)
            return;
        left.inorder();
        System.out.println(current_root + ", ");
        right.inorder();
    }//end inorder print

    /*public Node<T> Attack_of_the_clones()
    {

        left_copy = curr_node.left.copy();          
        right_copy = curr_node.right.copy();
        return new vertex(curr_node, left1, right1);
    }*/

    public vertex<T> largest(Node<T> x)
    {

        int left1 = largest(x.left);
        int right1 = right.largest();
        if(this.head > left1 && this.head > right1)
            return this.root;
        else
            return Math.max(left1,right1);
    }

}// end vertex

public class BinaryTree
{

    public static void main(String[] args)
    {
    Node<Integer> n = new vertex<Integer>(3);
    n = n.insert(4);
    for(int i = 0; i < 10; i++)
        {
        n.insert((int)Math.random*8);
        }
    n.size();
    n.depth();
    n.inorder();
    }//end main
}//end Binary Tree

BinaryTree.java:87: warning: [rawtypes] found raw type: vertex public Node<T> Attack_of_the_clones() { return new vertex(head, left.Attack_of_the_clones(), right.Attack_of_the_clones());} ^ missing type arguments for generic class vertex<T> where T is a type-variable: T extends Comparable<T> declared in class vertex BinaryTree.java:87: warning: [unchecked] unchecked call to vertex(T,Node<T>,Node<T>) as a member of the raw type vertex public Node<T> Attack_of_the_clones() { return new vertex(head, left.Attack_of_the_clones(), right.Attack_of_the_clones());} ^ where T is a type-variable: T extends Comparable<T> declared in class vertex BinaryTree.java:87: warning: [unchecked] unchecked conversion public Node<T> Attack_of_the_clones() { return new vertex(head, left.Attack_of_the_clones(), right.Attack_of_the_clones());} ^ required: Node<T> found: vertex where T is a type-variable: T extends Comparable<T> declared in class vertex 3 warnings

Answer 1

As Nil has no fields (is immutable) then its clone can just return itself.

//On Nil
public Node<T> myClone(){
   return this;
}

On Vertex you want to do a deep clone (cloning the fields instead of just copying their references).

//On Vertex
public Node<T> myClone(){
    return new Vertex<T>(head,left.myClone(),right.myClone())
}