none
Deep Copy in Binary Search Tree [Problem calling recursively] RRS feed

  • Question

  • Note: This is not Assignment. I am trying to implement Binary Search Tree for practice. I have seen two threads in this forum having trouble with BST deep copy. But couldn't get much help out of it.

    I have created a BinaryTree using instance BT and I want to deep copy the BST to another instance BS. The tree is being copied perfectly without sending pass by reference of BS instance rootNode, but this has no use when the the function call returns from the copying module it obviously looses the created tree. When i pass it by reference i have a problem calling it recursively in void BinaryTree::cloneBinaryTree(node* currentNode, node*& cloneTreeNode) function.

    Errors: 

    node *& cloneTreeNode

    Error: initial value of reference to non-const must be an lvalue.

    'BinaryTree::cloneBinaryTree' : cannot convert parameter 2 from 'node *' to 'node *&'

    From Main Program:

    BinaryTree BS(BT);

    Modules:

    struct node* BinaryTree::createNewNode(int itemValue){

    struct node *newNode = new node;
    newNode->setItemValue(itemValue);
    newNode->setLeftChild(NULL);
    newNode->setRightChild(NULL);
    return (newNode);
    }

    bool BinaryTree::isBinaryTreeEmpty(const BinaryTree& instance){ return (rootNode == NULL); }

    BinaryTree::BinaryTree(const BinaryTree& instance){
    if(isBinaryTreeEmpty(instance)) this->rootNode == NULL;
    else{
    this->rootNode= NULL;
    cloneBinaryTree(instance.rootNode, rootNode);
    }
    }

    void BinaryTree::cloneBinaryTree(node* currentNode, node*& cloneTreeNode){
    if(currentNode == NULL) return;
    else{
    cloneTreeNode = createNewNode(currentNode->getItemValue());
    cloneBinaryTree(currentNode->getLeftChild(), cloneTreeNode->getLeftChild());
    cloneBinaryTree(currentNode->getRightChild(), cloneTreeNode->getRightChild());
    }
    }

    Can you please suggest some solution to handle this problem,..?

    -Sathish

    Friday, March 9, 2012 3:19 AM

Answers

  • bool BinaryTree::isBinaryTreeEmpty(const BinaryTree& instance){ return (rootNode == NULL); }
    What is the role of parameter 'instance' here? You can drop it. Also mark the function as const, since you call this with const objects. bool BinaryTree::isBinaryTreeEmpty() const { return (rootNode == NULL); }
    BinaryTree::BinaryTree(const BinaryTree& instance){ if(isBinaryTreeEmpty(instance)) this->rootNode == NULL;
    I think you meant this->rootNode = NULL; here Also, change this as BinaryTree::BinaryTree(const BinaryTree& instance) { if (instance.isBinaryTreeEmpty()) this->rootNode = NULL; else { this->rootNode= NULL; cloneBinaryTree(instance.rootNode, rootNode); } }
    void BinaryTree::cloneBinaryTree(node* currentNode, node*& cloneTreeNode){ if(currentNode == NULL) return; else{ cloneTreeNode = createNewNode(currentNode->getItemValue()); cloneBinaryTree(currentNode->getLeftChild(), cloneTreeNode->getLeftChild()); cloneBinaryTree(currentNode->getRightChild(), cloneTreeNode->getRightChild()); } }
    If the getLeftChild() and getRightChild() are returning reference to the actual pointer, this should work like node*& getLeftChild() { return left; } node*& getRightChild() { return right; }
    • Marked as answer by Sathish5067 Friday, March 9, 2012 2:20 PM
    Friday, March 9, 2012 6:59 AM

All replies

  • bool BinaryTree::isBinaryTreeEmpty(const BinaryTree& instance){ return (rootNode == NULL); }
    What is the role of parameter 'instance' here? You can drop it. Also mark the function as const, since you call this with const objects. bool BinaryTree::isBinaryTreeEmpty() const { return (rootNode == NULL); }
    BinaryTree::BinaryTree(const BinaryTree& instance){ if(isBinaryTreeEmpty(instance)) this->rootNode == NULL;
    I think you meant this->rootNode = NULL; here Also, change this as BinaryTree::BinaryTree(const BinaryTree& instance) { if (instance.isBinaryTreeEmpty()) this->rootNode = NULL; else { this->rootNode= NULL; cloneBinaryTree(instance.rootNode, rootNode); } }
    void BinaryTree::cloneBinaryTree(node* currentNode, node*& cloneTreeNode){ if(currentNode == NULL) return; else{ cloneTreeNode = createNewNode(currentNode->getItemValue()); cloneBinaryTree(currentNode->getLeftChild(), cloneTreeNode->getLeftChild()); cloneBinaryTree(currentNode->getRightChild(), cloneTreeNode->getRightChild()); } }
    If the getLeftChild() and getRightChild() are returning reference to the actual pointer, this should work like node*& getLeftChild() { return left; } node*& getRightChild() { return right; }
    • Marked as answer by Sathish5067 Friday, March 9, 2012 2:20 PM
    Friday, March 9, 2012 6:59 AM
  • @FaisalIM.. Thanks for your response..!! I have made the 3 changes which you mentioned. It works perfectly. The problem was i didn't have my getLeftChild() and getRightChild() return by reference.

    Thanks again..!!

    -Sathish

    Friday, March 9, 2012 2:20 PM
  • Thank you for coming up with useful *& return method ! 
    Wednesday, November 20, 2019 4:19 AM