HOW IS A BINARY TREE COPIED RECURSIVELY?

[ayanda83]

Hi everyone, the function below was taken from a Data Structures textbook by D.S. Malik and its function is to deep copy a binary tree. The problem I'm having is that I don't understand how it works as it is implemented as a recursive function. I understand how the function works until line 11 but I don't understand line 12 and 13. can somebody explain how these two lines achieve deep copy.

template <class elemType>
void  binaryTreeType<elemType>::copyTree
                      (binaryTreeNode<elemType>* &copiedTreeRoot,
		               binaryTreeNode<elemType>* otherTreeRoot)
{
    if (otherTreeRoot == NULL)
        copiedTreeRoot = NULL;
    else
    {
        copiedTreeRoot = new binaryTreeNode<elemType>;
        copiedTreeRoot->info = otherTreeRoot->info;
        copyTree(copiedTreeRoot->llink, otherTreeRoot->llink);
        copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
    }
} //end copyTree 

[doug4]

The root node may or may not have a left node. It it does, that node is itself the root of a tree. So, line 12 calls the copyTree function using the left node as the root of the tree. And after the left node is copied, the right node is copied, too.

If the original tree has no left node, the recursive call to copyTree will execute line 7 and return. If the original tree does have a left node, lines 10-13 will be executed, and new the left and right subtrees will be copied.