How to deep copy a Binary Tree?

Question

I would like using my own Node class to implement tree structure in Java. But I'm confused how to do a deep copy to copy a tree.

My Node class would be like this:

public class Node{
private String value;
private Node leftChild;
private Node rightChild;
....

I'm new to recursion, so is there any code I can study? Thank you!

Solution 1

try

class Node {
    private String value;
    private Node left;
    private Node right;

    public Node(String value, Node left, Node right) {
        this.value = value;
        ...
    }

    Node copy() {
        Node left = null;
        Node right = null;
        if (this.left != null) {
            left = this.left.copy();
        }
        if (this.right != null) {
            right = this.right.copy();
        }
        return new Node(value, left, right);
    }
}

Solution 2

Doing it recursively using pre-order traversal.

    public static Node CopyTheTree(Node root)
    {
        if (root == null)
        {
            return null;
        }
        Node newNode = new Node(null, null, root.Value);
        newNode.Left= CopyTheTree(root.Left);
        newNode.Right= CopyTheTree(root.Right);
        return newNode;
    }

Solution 3

You can use something like this. It will go though the old tree depth first wise and create a copy of it.

private Tree getCopyOfTree(oldTree) {
 Tree newTree = new Tree();
 newTree.setRootNode(new Node());
 copy(oldTree.getRootNode(), newTree.getRootNode())
 return newTree;
}

private void copy(Node oldNode, Node newNode) {

 if (oldNode.getLeftChild != null) { 
  newNode.setLeftChild(new Node(oldNode.getLeftChild()));
  copy(oldNode.getLeftChild, newNode.getLeftChild()); 
 }

 if (oldNode.getRightChild != null) {
  newNode.setRightChild(new Node(oldNode.getRightChild()));
  copy(oldNode.getRightChild, newNode.getRightChild());
 }
}

Solution 4

I like Evgeniy Dorofeev's answer above, but sometimes you might not be able to add a method to the type Node as you might not own it. In that case(this is in c#):

public static TreeNode CopyTree(TreeNode originalTreeNode)
{
    if (originalTreeNode == null)
    {
        return null;
    }

    // copy current node's data
    var copiedNode = new TreeNode(originalTreeNode.Data);

    // copy current node's children
    foreach (var childNode in originalTreeNode.Children)
    {
        copiedNode.Children.Add(CopyTree(childNode));
    }

    return copiedNode;
}

View more solutions

Comments

[psi]

Using copy constructor Excellent.

[Uwe Plonus]

Can you please elaborate your answer and describe what it exactly does. Then the answer could also help other people also and not only the original poster.

[user2710322]

Sure. Sorry for the delay. Anyway... any recursive call has a base case, and one or more recursive cases. In this instance, the first line is obvious... if the method