Khronos Khronos - 1 year ago 74
Java Question

Java Binary Tree Cloning Problem

I have a Java Binary Tree with the below specification and I need to clone it.

public class Item {

private final String value;
public final Item left;
public final Item right;



What seems to be a very simple task has me baffled in that the cloned tree must share the same cells with the original tree object rather than being copied.

However if an item were to be added to either the original or cloned tree, it must not propagate to the other tree. ie. If a new item were to be added to the original tree, it must not appear in the cloned tree and vice vera.

Also this needs to be done without recursion and without any looping construct.

So I was wondering if anyone can think of anyway to do this because I have no idea where to start?

Answer Source

this can be done if you set up copy on write in the structure:

/*in Item */
Item add(String value){
   Item item = new Item(this.value);
      item.left = this.left;
      item.right = this.right.add(value);
      item.left = this.left.add(value);
      item.right = this.right;
   return item;

then the cloning is only copying the root to the other tree