Java deep copy - wrong reference assignment

Question

Please consider the following code

public class Pair implements Cloneable, Comparable<Para> {

    ...

    public Pair(String key, double value) throws Exception {
        if (value <= 0) throw new IllegalArgumentException();

        this.key = key;
        this.value = value;
    }

    ...

    @Override
    public Pair clone() throws CloneNotSupportedException {
        return (Pair) super.clone();
    }
}

and

public class BSTtree implements Dictionary, Cloneable {

    ...

    private class Node implements Cloneable, Comparable<Node> {
        Para elem;
        Node left = null;
        Node right = null;
        Node parent = null;

        Node () {
            this.elem = null;
        }

        Node (Pair elem) {
            this.elem = elem;
        }

        ...

        @Override
        public Node clone() throws CloneNotSupportedException {
            Node cloned = new Node();

            cloned.elem = elem.clone();
            if (left != null) cloned.left = left.clone();
            if (right != null) cloned.right = right.clone();

            return cloned;
        }
    }

    ...

    @Override
    public BSTtree clone() throws CloneNotSupportedException {
        BSTtree cloned = new BSTtree();
        cloned.root = root.clone();

        return cloned;
    }
}

I'm trying to implement my own BST tree having Cloneable interface. Where I have a problem is

BSTtree alfa = new BSTtree();
...
BSTtree beta = alfa.clone();

which I assume don't correctly set references to trees alfa and beta. Why do I think so? Take look at following

alfa.printTree(); //(VOID  1,00), (a  1,00), (b  2,00), (c  3,00), (e  5,00)
beta.printTree(); //(VOID  1,00), (a  1,00), (b  2,00), (c  3,00), (e  5,00)

beta.remove("a");

alfa.printTree(); //(VOID  1,00), (b  2,00), (c  3,00), (e  5,00)
beta.printTree(); //(VOID  1,00), (a  1,00), (b  2,00), (c  3,00), (e  5,00)

alfa.remove("e");

alfa.printTree(); //(VOID  1,00), (b  2,00), (c  3,00), (e  5,00)
beta.printTree(); //(VOID  1,00), (a  1,00), (b  2,00), (c  3,00), (e  5,00)

So you can see after cloning any removing from beta in fact removes from alfa, and removing from alfa does not remove at all. Of course before calling clone() every operation on alfa worked correctly.

This is for learning and the main task is to implement a working clone() method, so I don't want to use any other ways to perform a deep copy.

Please advise what am I doing wrong, as self-debugging haven't helped with it yet.

Answer 1

The parent update seems to be missing -- not sure if this is the only issue...

    @Override
    public Node clone() throws CloneNotSupportedException {
        Node cloned = new Node();

        cloned.elem = elem.clone();
        if (left != null) {
           cloned.left = left.clone();
           cloned.left.parent = cloned;
        }
        if (right != null) {
           cloned.right = right.clone();
           cloned.right.parent = cloned;
        }

        return cloned;
    }

P.S. I think the other issue is that the Node is a non-static inner class. So it always has an implicit pointer to the tree it was created in. Where you call new Node() in Node.clone, this is in the scope of the original tree, so it will still point to the original tree, but it needs to be an inner class of the new tree. Adding static to the inner class declaration will highlight the problem.

You may want to turn it into a static inner class and add an explicit pointer to the tree (if you need it -- some of the Node methods accessing root look like they should really be BSTtree methods).