Question

Add a clone method to the BST program. This method returns a deep copy of a tree. Coding Language C++

Use this main method to test your code:

int main()
{
Tree T;
T.insert(50);
T.insert(20);
T.insert(80);
T.insert(60);
T.insert(90);
T.display();
Tree T1 = T;
Tree T2 = T.clone();
cout << "\n\nT1 and T2 before insert(999)\n=====================\n\n";
T1.inOrder();
T2.inOrder();
T.insert(999);
cout << "\n\nT1 and T2 after insert(999)\n=====================\n\n";
T1.inOrder();
T2.inOrder();
system("pause"); // may need to remove this on some systems
return 0;
}

#include <iostream>

using namespace std;

//=====================================================================
struct Node {
int x;
Node * left;
Node * right;
};

//=====================================================================
class Tree
{
Node * root;
public:
Tree()
{
root = NULL;
}
  
//-----------------------------------------------------------------
void insert(int x)
{
Node * ptr = new Node;

ptr -> x = x;
ptr -> left = NULL;
ptr -> right = NULL;

cout << "\n-------------------------------------" << endl;
cout << "Node Address: " << ptr << endl;

if (root == NULL)
root = ptr;
else
{
Node * temp = root;

while (true)
{
if (temp -> x > x)
{
if (temp -> left == NULL) {
cout << "Node Parent Address: " << temp << endl;
cout << "Node Parent Value: " << temp -> x << endl;
temp -> left = ptr;
break;
} else
temp = temp -> left;
} else
{
if (temp -> right == NULL)
{
cout << "Node Parent Address: " << temp << endl;
cout << "Node Parent Value: " << temp -> x << endl;
temp -> right = ptr;
break;
} else
temp = temp -> right;
}
}
}

cout << "Root: " << root << endl;
cout << "-------------------------------------" << endl;
}
    

//-----------------------------------------------------------------
void remove(int value)
{
Node * temp = root, * ptemp = root;

while (temp != NULL && temp -> x != value)
{
ptemp = temp;
if (temp -> x < value)
temp = temp -> right;
else if (temp -> x > value)
temp = temp -> left;
}

if (temp == NULL) {
cout << "Value Not Found...." << endl;
} else
{
if (temp -> left == NULL && temp -> right == NULL)
{
if (temp == root)
root = NULL;
else if (ptemp -> left == temp)
ptemp -> left = NULL;
else if (ptemp -> right == temp)
ptemp -> right = NULL;
} else if (temp -> left == NULL && temp -> right != NULL)
{
if (temp == root)
root = temp -> right;
else if (ptemp -> left == temp)
ptemp -> left = temp -> right;
else if (ptemp -> right == temp)
ptemp -> right = temp -> left;
} else if (temp -> right == NULL && temp -> left != NULL)
{
if (temp == root)
root = temp -> left;
else if (ptemp -> left == temp)
ptemp -> left = temp -> left;
else if (ptemp -> right == temp)
ptemp -> right = temp -> right;
} else if (temp -> left != NULL && temp -> right != NULL)
{
Node * tempHolder = temp, * ptempHolder = temp;

while (tempHolder -> left != NULL)
{
ptempHolder = tempHolder;
tempHolder = tempHolder -> left;
}

temp -> x = tempHolder -> x;
ptempHolder -> left = tempHolder -> right;

temp = tempHolder;
}

delete temp;
cout << "Node Removed Successfully." << endl;
}
}
  
//-----------------------------------------------------------------
void deleteAllNodes(Node * temp) {
if (temp != NULL) {
deleteAllNodes(temp -> left);
deleteAllNodes(temp -> right);
cout << "Address: " << temp << endl;
cout << "Value: " << temp -> x << endl << endl;
delete temp;
}
}
  
//-----------------------------------------------------------------
~Tree() {
cout << "Below Nodes Deleted Successfully:" << endl;
deleteAllNodes(root);
}
};

Answer 1

//C++ program

#include <iostream>

using namespace std;

//=====================================================================
struct Node {
int x;
Node * left;
Node * right;
};

class Tree
{
Node * root;
public:
Tree()
{
root = NULL;
}

//-----------------------------------------------------------------
void insert(int x)
{
Node * ptr = new Node;

ptr -> x = x;
ptr -> left = NULL;
ptr -> right = NULL;

cout << "\n-------------------------------------" << endl;
cout << "Node Address: " << ptr << endl;

if (root == NULL)
root = ptr;
else
{
Node * temp = root;

while (true)
{
if (temp -> x > x)
{
if (temp -> left == NULL) {
cout << "Node Parent Address: " << temp << endl;
cout << "Node Parent Value: " << temp -> x << endl;
temp -> left = ptr;
break;
} else
temp = temp -> left;
} else
{
if (temp -> right == NULL)
{
cout << "Node Parent Address: " << temp << endl;
cout << "Node Parent Value: " << temp -> x << endl;
temp -> right = ptr;
break;
} else
temp = temp -> right;
}
}
}

cout << "Root: " << root << endl;
cout << "-------------------------------------" << endl;
}
  

//-----------------------------------------------------------------
void remove(int value)
{
Node * temp = root, * ptemp = root;

while (temp != NULL && temp -> x != value)
{
ptemp = temp;
if (temp -> x < value)
temp = temp -> right;
else if (temp -> x > value)
temp = temp -> left;
}

if (temp == NULL) {
cout << "Value Not Found...." << endl;
} else
{
if (temp -> left == NULL && temp -> right == NULL)
{
if (temp == root)
root = NULL;
else if (ptemp -> left == temp)
ptemp -> left = NULL;
else if (ptemp -> right == temp)
ptemp -> right = NULL;
} else if (temp -> left == NULL && temp -> right != NULL)
{
if (temp == root)
root = temp -> right;
else if (ptemp -> left == temp)
ptemp -> left = temp -> right;
else if (ptemp -> right == temp)
ptemp -> right = temp -> left;
} else if (temp -> right == NULL && temp -> left != NULL)
{
if (temp == root)
root = temp -> left;
else if (ptemp -> left == temp)
ptemp -> left = temp -> left;
else if (ptemp -> right == temp)
ptemp -> right = temp -> right;
} else if (temp -> left != NULL && temp -> right != NULL)
{
Node * tempHolder = temp, * ptempHolder = temp;

while (tempHolder -> left != NULL)
{
ptempHolder = tempHolder;
tempHolder = tempHolder -> left;
}

temp -> x = tempHolder -> x;
ptempHolder -> left = tempHolder -> right;

temp = tempHolder;
}

delete temp;
cout << "Node Removed Successfully." << endl;
}
}

//-----------------------------------------------------------------
void deleteAllNodes(Node * temp) {
if (temp != NULL) {
deleteAllNodes(temp -> left);
deleteAllNodes(temp -> right);
cout << "Address: " << temp << endl;
cout << "Value: " << temp -> x << endl << endl;
delete temp;
}
}

//-----------------------------------------------------------------
~Tree() {
cout << "Below Nodes Deleted Successfully:" << endl;
deleteAllNodes(root);
}

Node* cloneBinarySearchTree(Node *root){
    if(root == NULL)return NULL;
    /* create a copy of root node */
    Node* newNode = new Node;
    newNode->x = root->x;
    newNode->left = NULL;
    newNode->right = NULL;
    /* Recursively create clone of left and right sub tree */
    newNode->left = cloneBinarySearchTree(root->left);
    newNode->right = cloneBinarySearchTree(root->right);
    /* Return root of cloned tree */
    return newNode;
}

Tree clone(){
   Tree t;
   t.root = cloneBinarySearchTree(root);
   return t;
}

void inOrder(){
   inOrder(root);
   cout<<"\n";
}
void inOrder(Node* root){
   if(root == NULL) return;
   inOrder(root->left);
   cout<<root->x<<" ";
   inOrder(root->right);
}
};
int main()
{
Tree T;
T.insert(50);
T.insert(20);
T.insert(80);
T.insert(60);
T.insert(90);
T.inOrder();
Tree T1 = T;
Tree T2 = T.clone();
cout << "\n\nT1 and T2 before insert(999)\n=====================\n\n";
T1.inOrder();
T2.inOrder();
T.insert(999);
cout << "\n\nT1 and T2 after insert(999)\n=====================\n\n";
T1.inOrder();
T2.inOrder();
system("pause"); // may need to remove this on some systems
return 0;
}

//sample output