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!

Answer 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);
    }
}

Answer 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;
    }

Answer 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());
 }
}

Answer 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;
}

Answer 5

Not sure but try something with post order traversal of your tree and creating a new node for each node you traverse. You might require stack for storing the nodes you created to make left and right child links.

Answer 6

public static TreeNode copy( TreeNode source )
   {
      if( source == null )
         return null;
      else
         return new TreeNode( source.getInfo( ), copy( source.getLeft( ) ), copy( source.getRight( ) ) );
   }

/Sure. Sorry for the delay. Anyway... any recursive method has a base case, and one or more recursive cases. In this instance, the first line is obvious... if the argument to the parameter 'source' is null (as it eventually evaluates to in order to end the method's operation), it will return null; if not, the recursive case is initiated. In this case, you're returning the entire copied tree once the recursion is complete. The 'new' operator is used, indicating the instantiation of a TreeNode with each visit to the various nodes of the tree during the traversal, occurring through recursive calls to 'copy', whose arguments become references to the left and right TreeNodes (if there are any). Once source becomes null in each argument, the base case is initiated, releasing the recursion stack back to the original call to 'copy', which is a copy of the root of the original tree./

Answer 7

 Node copy(Node node)
  {
    if(node==null) return node;
    Node node1 =new Node(node.data);
    node1.left=copy(node.left);
    node1.right=copy(node.right);
    return node1;
  }