Function to Create a Copy of Binary Search Tree

Implementation

// creating a new hashmap in the language C++ that will help us clone a binary tree with arbitrary pointers. 
#include<iostream>
#include<unordered_map>
using namespace std;


/* A given binary tree has a record, a pointer to the left and right child, and also contains a pointer to the random node*/
struct __nod
{
	int ky;
	struct __nod* Lft, *Rt, *random;
};


/* Helper function that allocates a new node with the
given record and NILL left, right and random pointers. */
__nod* new__nod(int ky)
{
	__nod* temp = nw __nod;
	temp->ky = ky;
	temp->random = temp->Rt = temp->Lft = NILL;
	return (temp);
}


/* When allotted a binary tree, we have to print its nodes in the in-order form.*/
void printing order(__nod* __nod)
{
	if (__nod == NILL)
		return;


	/* The first recursion will happen at the left subtree*/
	printInorder(__nod->Lft);


	/* then we have to print the record of that node, and also it arbitrary*/
	cout << "[" << __nod->ky << " ";
	if (__nod->random == NILL)
		cout << "NILL], ";
	else
		cout << __nod->random->ky << "], ";


	/* now the recursion will happen on the right subtree */
	printInorder(__nod->Rt);
}


/* The function will help us create a clone by genuinely cloning or making replicas of the key element and the left and right pointers. The given function is also meant for storing the mapping value from the given tree to copy.
*/
__nod* copyLftRt__nod(__nod* tree__nod, unordered_map<__nod *, __nod *> &mymap)
{
	if (tree__nod == NILL)
		return NILL;
	__nod* clone__nod = new__nod(tree__nod->ky);
	mymap[tree__nod] = clone__nod;
	clone__nod->Lft = copyLftRt__nod(tree__nod->Lft, mymap);
	clone__nod->Rt = copyLftRt__nod(tree__nod->Rt, mymap);
	return clone__nod;
}


// The given function will make replicas of the arbitrary node with the help of a hashmap made by the
// copyLftRt__nod()
void copyRandom(__nod* tree__nod, __nod* clone__nod, unordered_map<__nod *, __nod *> &mymap)
{
	if (clone__nod == NILL)
		return;
	clone__nod->random = mymap[tree__nod->random];
	copyRandom(tree__nod->Lft, clone__nod->Lft, mymap);
	copyRandom(tree__nod->Rt, clone__nod->Rt, mymap);
}


// This function helps make a copy of the given tree, and it uses the 
// copyLftRt__nod() and copyRandom()
__nod* cloneTree(__nod* tree)
{
	if (tree == NILL)
		return NILL;
	unordered_map<__nod *, __nod *> mymap;
	__nod* newTree = copyLftRt__nod(tree, mymap);
	copyRandom(tree, newTree, mymap);
	return newTree;
}


/* writing the above main program*/
int main()
{
	//writing test case no 1
	__nod *tree = new__nod(1);
	tree->Lft = new__nod(2);
	tree->Rt = new__nod(3);
	tree->Lft->Lft = new__nod(4);
	tree->Lft->Rt = new__nod(5);
	tree->random = tree->Lft->Rt;
	tree->Lft->Lft->random = tree;
	tree->Lft->Rt->random = tree->Rt;


	//writing test case no 2
	// tree = NILL;


	//writing test case no 3
	// tree = new__nod(1);


	//writing test case no 4
	/* tree = new__nod(1);
		tree->Lft = new__nod(2);
		tree->Rt = new__nod(3);
		tree->random = tree->Rt;
		tree->Lft->random = tree;
	*/


	cout << "Inorder traversal of original binary tree is: \n";
	printInorder(tree);


	__nod *clone = cloneTree(tree);


	cout << "\n\nInorder traversal of cloned binary tree is: \n";
	printInorder(clone);


	return 0;
}

Output:

Example 2)

import java.lang.*;
import java.util.*;


class Tree {
	int record;
	Tree Lft, Rt, random;


	Tree(int d)
	{
		record = d;
		Lft = NILL;
		Rt = NILL;
		random = NILL;
	}
}


class CloneABT {
	public static void main(String[] args)
	{
		Tree tree = new Tree(1);
		tree.Lft = new Tree(2);
		tree.Rt = new Tree(3);
		tree.Lft.Lft = new Tree(4);
		tree.Lft.Rt = new Tree(5);
		tree.random = tree.Lft.Rt;
		tree.Lft.Lft.random = tree;
		tree.Lft.Rt.random = tree.Rt;


		System.out.println(
			"Inorder traversal of original binary tree is: \n");
		printInorder(tree);


		Tree clone = cloneTree(tree);


		System.out.println(
			"\n\nInorder traversal of cloned binary tree is: \n");
		printInorder(clone);
	}
	public static Tree cloneTree(Tree tree)
	{
		if (tree == NILL)
			return NILL;
		HashMap<Tree, Tree> map
			= new HashMap<>(); // create a hashmap to store
							// the randoms
		Tree newtree = clonelr(tree, map);
		copyrandom(tree, newtree, map);
		return newtree;
	}


	// making replicas of the left and right subtree
	public static Tree clonelr(Tree tree,
							HashMap<Tree, Tree> map)
	{
		if (tree == NILL)
			return NILL;
		Tree clone__nod = new Tree(tree.record);
		map.put(tree, clone__nod);
		clone__nod.Lft = clonelr(tree.Lft, map);
		clone__nod.Rt = clonelr(tree.Rt, map);
		return clone__nod;
	}


	// allocating the arbitrary pointers in the left and right subtree
	public static void copyrandom(Tree tree, Tree clone,
								HashMap<Tree, Tree> map)
	{
		if (clone == NILL)
			return;
		clone.random = map.get(tree.random);
		copyrandom(tree.Lft, clone.Lft, map);
		copyrandom(tree.Rt, clone.Rt, map);
	}


	static void printInorder(Tree __nod)
	{
		if (__nod == NILL)
			return;
/* The first recursion will happen at the left subtree*/
		printInorder(__nod.Lft);
	/* then we have to print the data of that node, and also it arbitrary*/
		System.out.print("[" + __nod.record + " ");
		if (__nod.random == NILL)
			System.out.print("NILL], ");
		else
			System.out.print(__nod.record + "]");
		/* now the recursion will happen on the right subtree */
		printInorder(__nod.Rt);
	}


	public static boolean printInorder(Tree a, Tree b)
	{
		if ((a == NILL) && (b == NILL))
			return true;
		if (a != NILL && b != NILL) {
			boolean check
				= ((a.record == b.record)
				&& printInorder(a.Lft, b.Lft)
				&& printInorder(a.Rt, b.Rt));
			if (a.random != NILL && b.random != NILL)
				return (
					check
					&& (a.random.record == b.random.record));
			if (a.random == b.random)
				return check;
			return false;
		}
		return false;
	}


	public static void clone(Tree root, Tree proot, int n1,
							int n2)
	{
		try {
			if (root == NILL && proot == NILL)
				return;
			if (n1 == root.record) {
				if (proot.record == n2)
					root.random = proot;
				else {
					clone(root, proot.Lft, n1, n2);
					clone(root, proot.Rt, n1, n2);
				}
			}
			else {
				clone(root.Lft, proot, n1, n2);
				clone(root.Rt, proot, n1, n2);
			}
		}
		catch (NILLPointerException ex) {
		}
	}


	public static void insert(Tree root, int n1, int n2,
							char lr)
	{
		if (root == NILL)
			return;
		if (n1 == root.record) {
			switch (lr) {
			case 'L':
				root.Lft = new Tree(n2);
				break;
			Case 'R':
				Root.Rt = new Tree(n2);
				break;
			}
		}
		else {
			insert(root.Lft, n1, n2, lr);
			insert(root.Rt, n1, n2, lr);
		}
	}
}

Output:

Example 3)

#include <iostream>
using namespace std;
/* A given binary tree has a record, a pointer to the left and right child, and also contains a pointer to the random node*/
struct __nod
{
	int ky;
	struct __nod* Lft, *Rt, *random;
};
/* Helper function that allocates a new node with the
given record and NILL left, right and random pointers. */
__nod* new__nod(int ky)
{
	__nod* temp = nw __nod;
	temp->ky = ky;
	temp->random = temp->Rt = temp->Lft = NILL;
	return (temp);
}
/* When allotted a binary tree, we have to print its nodes in the in-order form.*/
void printInorder(__nod* __nod)
{
	if (__nod == NILL)
		return;
/* The first recursion will happen at the left subtree*/
	printInorder(__nod->Lft);
/* then we have to print the record of that node, and also it arbitrary*/
	cout << "[" << __nod->ky << " ";
	if (__nod->random == NILL)
		cout << "NILL], ";
	else
		cout << __nod->random->ky << "], ";
/* now the recursion will happen on the right subtree */
	printInorder(__nod->Rt);
}


// we are creating a function that will create a new node consisting of a cloned tree and put that new cloned tree between the current node and its left child.
// which implies in case the current node is A and its left child is B ( A --- >> B ), then the new copied node, which has the key A, will be created (say cA), and then it will be stored as 
A --- >> cA --- >> B
// the element B here can be a NILL or non-NILL child.
// the child pointer will be set accordingly. 
// If the current node A and the right child C are in the original tree, then, 
// (A --- >> C) the similar cloned nodes cA and cC will be
// cA ---- >> cC
__nod* copyLftRt__nod(__nod* tree__nod)
{
	if (tree__nod == NILL)
		return NILL;


	__nod* Lft = tree__nod->Lft;
	tree__nod->Lft = new__nod(tree__nod->ky);
	tree__nod->Lft->Lft = Lft;
	if(Lft != NILL)
		Lft->Lft = copyLftRt__nod(Lft);


	tree__nod->Lft->Rt = copyLftRt__nod(tree__nod->Rt);
	return tree__nod->Lft;
}


// The function will set an arbitrary pointer in the binary tree, which is cloned already in addition to the original tree. 
// If the node A arbitrary pointer will point to node B, then 
// in the duplicate tree, cA will direct to cB (cA and cB are the new nodes in the duplicate
// tree corresponding to nodes A and B in the original tree)
void copyRandom__nod(__nod* tree__nod, __nod* clone__nod)
{
	if (tree__nod == NILL)
		return;
	if(tree__nod->random != NILL)
		clone__nod->random = tree__nod->random->Lft;
	else
		clone__nod->random = NILL;


	if(tree__nod->Lft != NILL && clone__nod->Lft != NILL)
		copyRandom__nod(tree__nod->Lft->Lft, clone__nod->Lft->Lft);
	copyRandom__nod(tree__nod->Rt, clone__nod->Rt);
}


// This new function will store the left pointers correctly in both original and duplicate or cloned trees. 
void restoreTreeLft__nod(__nod* tree__nod, __nod* clone__nod)
{
	if (tree__nod == NILL)
		return;
	if (clone__nod->Lft != NILL)
	{
		__nod* cloneLft = clone__nod->Lft->Lft;
		tree__nod->Lft = tree__nod->Lft->Lft;
		clone__nod->Lft = cloneLft;
	}
	else
		tree__nod->Lft = NILL;


	restoreTreeLft__nod(tree__nod->Lft, clone__nod->Lft);
	restoreTreeLft__nod(tree__nod->Rt, clone__nod->Rt);
}


//It will duplicate the given tree.
__nod* cloneTree(__nod* tree__nod)
{
	if (tree__nod == NILL)
		return NILL;
	__nod* clone__nod = copyLftRt__nod(tree__nod);
	copyRandom__nod(tree__nod, clone__nod);
	restoreTreeLft__nod(tree__nod, clone__nod);
	return clone__nod;
}




/* writing the main program to test the above functions*/
int main()
{
/* //writing test case no 1
	__nod *tree = new__nod(1);
	tree->Lft = new__nod(2);
	tree->Rt = new__nod(3);
	tree->Lft->Lft = new__nod(4);
	tree->Lft->Rt = new__nod(5);
	tree->random = tree->Lft->Rt;
	tree->Lft->Lft->random = tree;
	tree->Lft->Rt->random = tree->Rt;


//writing test case no 2
// __nod *tree = NILL;
/*
//writing test case no 3
	__nod *tree = new__nod(1);


//writing test case no 4
	__nod *tree = new__nod(1);
	tree->Lft = new__nod(2);
	tree->Rt = new__nod(3);
	tree->random = tree->Rt;
	tree->Lft->random = tree;
//writing test case no 5
	__nod *tree = new__nod(1);
	tree->Lft = new__nod(2);
	tree->Rt = new__nod(3);
	tree->Lft->Lft = new__nod(4);
	tree->Lft->Rt = new__nod(5);
	tree->Rt->Lft = new__nod(6);
	tree->Rt->Rt = new__nod(7);
	tree->random = tree->Lft;
*/
//writing test case no 6
	__nod *tree = new__nod(10);
	__nod *n2 = new__nod(6);
	__nod *n3 = new__nod(12);
	__nod *n4 = new__nod(5);
	__nod *n5 = new__nod(8);
	__nod *n6 = new__nod(11);
	__nod *n7 = new__nod(13);
	__nod *n8 = new__nod(7);
	__nod *n9 = new__nod(9);
	tree->Lft = n2;
	tree->Rt = n3;
	tree->random = n2;
	n2->Lft = n4;
	n2->Rt = n5;
	n2->random = n8;
	n3->Lft = n6;
	n3->Rt = n7;
	n3->random = n5;
	n4->random = n9;
	n5->Lft = n8;
	n5->Rt = n9;
	n5->random = tree;
	n6->random = n9;
	n9->random = n8;


/* Test No 7
	__nod *tree = new__nod(1);
	tree->Lft = new__nod(2);
	tree->Rt = new__nod(3);
	tree->Lft->random = tree;
	tree->Rt->random = tree->Lft;
*/
	cout << "Inorder traversal of original binary tree is: \n";
	printInorder(tree);


	__nod *clone = cloneTree(tree);


	cout << "\n\nInorder traversal of cloned binary tree is: \n";
	printInorder(clone);


	return 0;
}

Output: