Logo
×

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:

Function to Create a Copy of Binary Search Tree

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:

Function to Create a Copy of Binary Search Tree

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:

Function to Create a Copy of Binary Search Tree

Related Topics

Cycle sort

Cycle sort is an examination arranging calculation which powers exhibit to be figured into the quantity of cycles where every one of them can be pivoted to create an arranged...

5 minutes read.

What are Forest Trees in Data Structure

Data structure A data model manages and optimizes computer resources, and a database stores and manages data. It's one of many uses for data structures to hold data. Data structures come...

5 minutes read.

Lowest Common Ancestor in a Binary Tree

The lowest node in the tree that contains both n1 and n2 as descendants is the lowest common ancestor (LCA), and n1 and n2 are the nodes for which we...

11 minutes read.

Length of longest palindrome in a linked list using O(1) extra space

Length of longest palindrome in a linked list using O(1) extra space In this problem, we need to find the length of the longest palindrome list that is present in given...

2 minutes read.

Data Structures Algorithms

What is an Algorithm? An algorithm is a sequence of steps used to complete a job or get a desired result. It is similar to programming building elements that let cell...

4 minutes read.

Inorder Successor in Binary Trees

The next node in the Inorder traversal of a binary tree is known as Inorder successor of that particular node. In a Binary Search Tree, the definition of Inorder successor can...

9 minutes read.

Optimal binary search tree using dynamic programming

Implementation // We are creating a presentation where we will present a recursive method of the optimal binary search tree problem.  #include <bits/stdc++.h> using namespace std; //creating a utility function that will help us...

9 minutes read.

Implementation of Queue

Implementation of queue: We can implement the queue through the array and linked list. An array is the easiest way to implement the queue. When a queue is created with the...

7 minutes read.

AVL tree in data structure c++

AVL tree is generally known as the self-sustained and most balanced tree in the field of a binary search tree. It was also widely known as the height-balanced binary tree....

6 minutes read.

Write Main Difference Between Tree and Graph in Data Structures

Graph: The graph has two sets, which are considered V and E. These vertices are also called nodes, and edges are referred to as arcs connecting any two nodes in a...

4 minutes read.

Convert Binary Tree into a Threaded Binary Tree

Implementation /*Writing a C++ program that will help us change the binary tree into a threaded binary tree and help us transform. */ #include <bits/stdc++.h> using namespace std; /*Creating the structure of a node...

11 minutes read.

Binary Search Tree vs AVL Tree: Data Structure

Difference Between Binary Search Tree and AVL Tree Binary Search Tree: The binary search tree is a kind of binary tree data structure and it follows the conditions of binary...

3 minutes read.

Find out the area between two concentric circles

You have given two values of the radius of two circles. You have to find out the area between these two circles. Let's take an example - For the above diagram,...

3 minutes read.

Bubble Sort vs Heap Sort

In this article, we are going to compare the two most common sorting techniques, Bubble Sort and Heap sort. Before discussing their differences, let us first discuss the idea of...

7 minutes read.

Stack vs Queue: Data Structure

 Difference Between Stack and Queue What is Stack? The LIFO principle applies on insertion and deletion operations of the stack which means last inserted element to the stack will remove first....

3 minutes read.

Asynchronous advantage actor-critic (A3C) Algorithm

The Asynchronous advantage actor-critic (A3C) Algorithm is one of the latest algorithms developed by the Artificial Intelligence division, Deep Mind at Google. It is used for the Deep Reinforcement Learning...

3 minutes read.

What is the difference between Tree and Graph

We usually use a diverse range of data structure to store our data and information. To store them in a more sequential manner and to access them easily, we use...

4 minutes read.

Program to calculate the area of the circumcircle of an equilateral triangle

You have given one value which represents the side of the equilateral triangle. You have to find out the area of the circumcircle. Let’s take an example - For the above...

3 minutes read.

Perfect Binary Tree

Complete binary trees are an important and general topic in the concept – of tree data structures. Before discussing a complete binary tree, we need to know the concept of...

4 minutes read.

Difference Between Linear and Non Linear Data Structures

Data Structure A data structure is a data object together with the relationships between the instances and the individual elements that compose an instance. These relationships are defined by the operations...

5 minutes read.