Copy binary tree in order

Question

The code I wrote so far is:

void copyInOrder(TNode *orgTree, Tnode *& copyTree){
    if(orgTree !=NULL){
        copyInOrder(orgTree->left_link);
        //create leftmost node of tree but how to link to parent
        copyInOrder(orgTree->right_link);
    }
}

I dont know how to link to the parent to the nodes as its inorder.

Answer 1

I think it would be something like this.

void copyInOrder(TNode *orgTree, Tnode *& copyTree){
    if(orgTree !=NULL){
        //left side
        TNode newLeftNode = cloneNode(orgTree->left_link);
        copyTree->left_link = newLeftNode;
        copyInOrder(orgTree->left_link, copyTree->left_link);

        //right side
        TNode newRightNode = cloneNode(orgTree->right_link);
        copyTree->right_link = newRightNode;
        copyInOrder(orgTree->right_link, copyTree->right_link);
    }
}

Answer 2

Suppose orgTree points to root (2). For copying, we have to do the following:

1. create a node at copyTree, and the copy the value 2 into it
2. if orgTree->left != NULL, call copyInOrder( orgTree->left, copyTree->left );
3. if orgTree->right != NULL, call copyInOrder( orgTree->right, copyTree->right );

BTW, this type of traversal is known as pre-order traversal, in-order traversal is different.