Binary Search Tree - Copying a tree

14,422

Your declaration of treeNew creates a call-by-value parameter. This means changes to this variable are never seen by the caller. You must make this a reference parameter, so the caller's pointer can be modified. Then recursively copying the subtrees is very simple:

void BST<T>::copyBST(Node* treeOriginal, Node *parent, Node*& treeNew){

    if (treeOriginal == NULL) //base case to end recursion when at tree end
        treeNew == NULL;
    else{
        Node* treeNew = new Node;  //create the node and set the new key to original
        treeNew->key = treeOriginal->key;
        treeNew->parent = parent;

        // Just call recursively to copy the subtrees:
        copyBST(treeOriginal->left, treeNew, treeNew->left);
        copyBST(treeOriginal->right, treeNew, treeNew->right);
    } 
}

Note the & added to the second parameter type. A more common idiom is to use the function return value:

Node* BST<T>::copyOf(Node* treeOriginal, Node *parent){

    if (treeOriginal == NULL) //base case to end recursion when at tree end
        return NULL;

    //create the node and set the new key to original
    Node* treeNew = new Node;
    treeNew->key = treeOriginal->key;
    treeNew->parent = parent;

    // Just call recursively to copy the subtrees:
    treeNew->left = copyOf(treeOriginal->left, treeNew);
    treeNew->right = copyOf(treeOriginal->right, treeNew);

    return treeNew;
}
Share:
14,422
Admin
Author by

Admin

Updated on June 04, 2022

Comments

  • Admin
    Admin over 1 year

    I'm messing around with sorting data structures in C++ so I'm writing a bunch of functions to make a binary search tree class. I'm a bit lost when trying to create a copy constructor/function to copy a tree.

    void BST<T>::copyBST(Node* treeOriginal, Node* treeNew){
    
            if (treeOriginal == NULL) //base case to end recursion when at tree end
                treeNew == NULL;
            else{
                Node* treeNew = new Node;  //create the node and set the new key to original
                treeNew->key = treeOriginal->key;
    
                Node* leftChild = new Node; //create a left node to be child of new node
                treeNew->left = leftChild;
                leftChild->parent = treeNew;
    
                Node* rightChild = new Node; //create a right node
                treeNew->right = rightChild;
                rightChild->parent = treeNew;
    
                copyBST(treeOriginal->left, leftChild); //call copy function on subtree of left child
                copyBST(treeOriginal->right, rightChild); //call copy function on subtree of right child
            } 
    }
    

    Now a few things happen when I try run this. First, it doesn't copy all of the nodes, and will copy a different amount each time. This is strange to me since I'm calling a recursion on every node, since I start at the root and then call it on the left and right. I tried writing out the process on paper, visually planning out how it would copy the original tree but to me it seems like a logical process and can't find where it could get lost.

    I also added cout statements in the function to print out the original node's key, address, parent, and children, as well as the copy node's key, address, parent and children. The only problem I found in this test was that the copy node's parent address was always 00000000, or NULL. So apparently the piece of code

    leftChild->parent = treeNew; and rightChild->parent = treeNew;
    

    doesn't actually set the node's parent pointer to the parent.

    These were the only clear issues I could find while trying to fix this. I'm not sure how else to look for the problem. If you can't see any problems in the logic of the code, does anyone have any other ideas of how to find where the problem lies?

    Thank you!