Question

(C++) I need to Create a Copy function of a Binary Search Tree recursively providing these structure

emplate <typename T>
class Tree
{
   struct TreeNode
   {
       T mData;
       TreeNode* mLeft = nullptr;
       TreeNode* mRight = nullptr;
       TreeNode* mParent = nullptr;

       bool mIsDead = false;

       TreeNode()
       {
       }
       TreeNode(T tData) : TreeNode()
       {
           mData = tData;
       }
   };
   TreeNode* mHead;

   // This tree wants a copy of that node and all beneath it
   void CopyTree(TreeNode* tNode)
   {
       if (tNode != nullptr)
       {

}

   }

There is an Add function below this, so you can use this to call recursively

void Add(T tWhat)
   {
       if (mHead == nullptr)
       {
           mHead = new TreeNode(tWhat);
           return;
       }

       TreeNode* tWalker = mHead;
       while (true)
       {
  
           if (tWalker->mData == tWhat)
           {
               tWalker->mIsDead = false;// Might already be false. Don't care.
               break;
           }
           else if (tWalker->mData > tWhat)// I want to go left
           {
               if (tWalker->mLeft == nullptr)// But I'm at the end so I'll just put this there.
               {
                   tWalker->mLeft = new TreeNode(tWhat);
                   tWalker->mLeft->mParent = tWalker;
                   break;
               }
               else
                   tWalker = tWalker->mLeft;
           }
           else
               if (tWalker->mRight == nullptr)
               {
                   tWalker->mRight = new TreeNode(tWhat);
                   tWalker->mRight->mParent = tWalker;
                   break;
               }
               else
                   tWalker = tWalker->mRight;
       }
   }

my main:

Tree<int> tTreeOne;
   tTreeOne.Add(50);
   tTreeOne.Add(30);
   tTreeOne.Add(80);

Tree<int> tTreeTwo(tTreeOne);

Answer 1

Below is the program providing the copy function for the Btree nodes.

How It works: It traverse the tree in preorder mode(root, leftnode, rightnode). This provides the information on the root node first and then the child nodes. As the program visit new node in tree to be copied it takes the value in visited node and adds the value in that node to new tree. Thus having the resultant tree a copy of provided tree.

There are few things lacking in the program provided, so added on my own.

1. Added printTree method to print all the nodes of tree in postOrder (leftNode, RightNode, root) form, this helps in listing the nodes and thus comparing the result.

2. Tree constructor to make mHead = nullptr at the time of instantiation of object.
3. getHead method : Since mHead will be a private data, to get the root node some get method is required.
4. CopyTree method takes TreeNode* as argument and not the Tree so getMethod is required, as mentioned above.

5. What is basically sought is a copy constructor, so both solution is provided, CopyTree function is provided as asked in question and also the copy constructor which is usually the way to do such copy.

Usage of both is provide in main function.

=====

Working of CopyTree: It visits the node provided and then uses the value in that node to call Add of the destination tree. After this it traverse both left and right branches if they are not null. If not null it calls itself recursively with that new node.

Refer to inline content for more description.

#include <iostream>
using namespace std;

template <typename T>
class Tree
{
struct TreeNode
{
T mData;
TreeNode* mLeft = nullptr;
TreeNode* mRight = nullptr;
TreeNode* mParent = nullptr;

bool mIsDead = false;

TreeNode()
{
}
TreeNode(T tData) : TreeNode()
{
mData = tData;
}
};
TreeNode* mHead;

void printNodes(TreeNode* tWalker)
{ //Calls itself for left node if not null
if(tWalker->mLeft)
{
printNodes(tWalker->mLeft);
}

//prints the data in this root node.
cout<< " " << tWalker->mData;

//Calls itself for right node if not null.
if(tWalker->mRight)
{
printNodes(tWalker->mRight);
}
}
public:

//This is copy constructor
Tree(Tree &tNode)
{
mHead = nullptr; //Call of copy constructor would avoid usual constructor so initializing here also.
CopyTree(tNode.getHead());
}
// This tree wants a copy of that node and all beneath it
void CopyTree(TreeNode* tNode)
{
if (tNode != nullptr)
{
Add(tNode->mData); //Add data

CopyTree(tNode->mLeft); //Call recursively for left node
CopyTree(tNode->mRight); //Call recursively for right node
}

}
//Constructor to make mHead null at the time of creation

Tree()
{
mHead = nullptr;
}

//Return the value of head node pointer of a tree as mHead is private data.
TreeNode* getHead()
{
return mHead;
}
//No change in Add function
void Add(T tWhat)
{
if (mHead == nullptr)
{
mHead = new TreeNode(tWhat);
return;
}

TreeNode* tWalker = mHead;
while (true)
{
  
if (tWalker->mData == tWhat)
{
tWalker->mIsDead = false;// Might already be false. Don't care.
break;
}
else if (tWalker->mData > tWhat)// I want to go left
{
if (tWalker->mLeft == nullptr)// But I'm at the end so I'll just put this there.
{
tWalker->mLeft = new TreeNode(tWhat);
tWalker->mLeft->mParent = tWalker;
break;
}
else
tWalker = tWalker->mLeft;
}
else
if (tWalker->mRight == nullptr)
{
tWalker->mRight = new TreeNode(tWhat);
tWalker->mRight->mParent = tWalker;
break;
}
else
tWalker = tWalker->mRight;
}
}
void printTree()
{
cout << "\n";
if(mHead)
printNodes(mHead);
else
cout << "Tree Empty";
}
};

int main()
{
Tree<int> tTreeOne;
tTreeOne.Add(50);
tTreeOne.Add(30);
tTreeOne.Add(80);
tTreeOne.Add(70);

tTreeOne.printTree();

// Now creating tree 2 by explicitly calling CopyTree method
Tree<int> tTreeTwo;

tTreeTwo.CopyTree(tTreeOne.getHead());
tTreeTwo.printTree(); //This would give data same as tree1

tTreeTwo.Add(170); //Making changes to tree2
tTreeTwo.printTree();

Tree<int> tTreeThree(tTreeTwo); //creating tree3 as copy of tree2 but using copy constructor.

tTreeThree.printTree(); //tree3 print will be same as print of tree2
}

Compilation: g++ <filename>
No additional flag are required.

Output in Cygwin:

30 50 70 80 -- listing of first tree
30 50 70 80 -- listing of second tree create by call to CopyTree
30 50 70 80 170 -- listing after adding node 70 to tree2
30 50 70 80 170 -- listing of tree3 created using copy constructor from tree2