Data Structures, Algorithms, & Applications in Java
Chapter 12, Exercise 25

In writing the cloning codes, we assume that we are not to make clones of the elements in the nodes. Only the tree structure is to be cloned. In case the elements are also to be cloned, then we must replace all occurrences of element by code to first cast element into a CloneableObject, and then invoke the method clone on the reulting object.

The codes for the two cloning methods are given below. 
public class BinaryTreeCloning
{
   /** preorder cloning
     * @return root of clone */
   public static BinaryTreeNode preOrderClone(BinaryTreeNode t)
   {
      if (t != null)
      {// nonempty tree
         // make a clone of the root
         BinaryTreeNode ct = new BinaryTreeNode(t.element);

         // now do the subtrees
         ct.leftChild = preOrderClone(t.leftChild);    // clone left subtree
         ct.rightChild = preOrderClone(t.rightChild);  // clone right subtree
         return ct;
      }
      else
         return null;
   }

   /** postorder cloning
     * @return root of clone */
   public static BinaryTreeNode postOrderClone(BinaryTreeNode t)
   {
      if (t != null)
      {// nonempty tree
         // clone left subtree
         BinaryTreeNode cLeft = postOrderClone(t.leftChild);

         // clone right subtree
         BinaryTreeNode cRight = postOrderClone(t.rightChild);

         // clone root
         return new BinaryTreeNode(t.element, cLeft, cRight);
      }
      else
         return null;
   }
}


The recursion stack space needed by both the preorder and postorder copy methods is O(h), where h is the height of the binary tree being cloned.

A test program and output can be found in the files BinaryTreeCloning.*.