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

Binary Tree vs Binary Search Tree: Data Structure

Difference Between Binary Tree and Binary Search Tree What is Binary Tree? A tree which each node can have utmost two children called binary tree. These children are referred as the ‘left...

3 minutes read.

Big O Notations

What is Big O Notation, and why is it important? "Big O notation is a mathematical notation that depicts a function's limiting behaviour when the input tends towards a certain value...

10 minutes read.

String Operations in Data Structures

Operations on Strings Reversing the order of words in a sentence Reversing a string is a technique that reverses or alters the order of a given string so that the last character...

9 minutes read.

Given a Binary Tree Print the Shortest Path

Implementation // Writing a program in C++ to find the shortest between the nodes i and j.  #include <bits/stdc++.h> using namespace std; // the given function will print the path between nodes i and...

7 minutes read.

Identical Linked Lists

Identical Linked Lists In this problem, we have given two linked lists, and we need to check whether the given linked lists are identical or not. Identical means they have the...

4 minutes read.

Common Operations on various Data Structures

Data structures are ways to organise data in computer memory for quick and effective use. The storage of data uses a variety of data-structures. It is also possible to define...

7 minutes read.

Bookshop management system using file handling in C++

We see different software in every hospitals or library to manage their database. It is very important to store organization’s data. So we use this software. Now we are going...

5 minutes read.

Breadth First Search

Breadth First Search Breadth first search is a graph traversing algorithm. In this, we start traversing from the source node or any selected node and traverse the graph layer by layer....

6 minutes read.

Hashing

Hashing: Hashing is a process in which a large amount of data is mapped to a small table with the help of hashing function. It is a searching technique. Hash table We...

4 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.

Burning binary tree

Burn the Binary tree starting from the target node You have given a binary tree and a target node value. Now you have to burn the tree from target node. You...

4 minutes read.

Array vs Linked List: Data Structure

Data structure: Difference Between Array and Linked List What is Array? An array is a linear data structure that can store similar data items for further processing. The similar data items...

3 minutes read.

Bubble Sort vs Merge Sort

In this article, we are going to compare two sorting techniques, Bubble sort and Merge Sort. In starting, we will first discuss the idea of sorting an array using bubble...

7 minutes read.

What is the B+ Tree in Data Structures?

We all know that the B+ tree in data structures is nothing but just an extended version of the B tree. It allows the smooth working of all the operations...

7 minutes read.

Adding one to the number represented an array of digits

You have given one array, which consists of values which represent the different digits of a number. You have to add 1 to this number and store the result in...

3 minutes read.

Tim Sort

Tim Sort is a mixture stable arranging calculation that exploits normal examples in information, and uses a mix of an improved Merge sort and Binary Insertion sort alongside an interior...

6 minutes read.

Hash Table vs STL Map

Hash table and STL map are extremely valuable information structures in software engineering. Here we will consider the examination between their properties to be well as execution.  To start with, we will...

7 minutes read.

Find Bridges in a Graph

You have been given a graph. You have to find out the bridges in that graph. Graph may be connected or disconnected. You have to print vertices of particular edge...

4 minutes read.

Queue Data Structure

Queue in DS: The queue is a non-primitive and linear data structure. It works on the principle of FIFO (First In First Out). That is, the element that is added...

4 minutes read.

Introduction and Implementation of Bloom Filter

It often happens with many of us that when we create an account on some applications like Github, it shows us that the username already exists. You can add some...

4 minutes read.