# Program to Clone a Binary Tree with Random Pointers

• Write a program in C to clone a Binary tree having random pointer.
• How to clone a binary tree with random pointer.

Given a binary tree with a random pointer in every node, we have to create a duplicate of input binary tree. Below is the structure of binary tree node with random pointer.

```struct node {
int data;
struct node *left;
struct node *right;
struct node *random;
};
```

The random pointer of a node can point to any node of tree or can even point to NULL. In this program, we will use a map of node pointers. While cloning binary tree, we will populate the address of original tree node and corresponding node in duplicate tree so that we will have a one to one mapping between old and corresponding new nodes.

Algorithm to clone a binary tree with random pointer
Let "root" be the root node of binary tree.
• Create an Empty map. Where key and value both are node pointers.
• Traverse given binary tree using pre Order traversal and clone root node.
• After cloning, put the address of root and new node in a map.
• Recursively clone left and right sub tree of make it left and right sub tree of new node.
• Now, traverse duplicate tree and populate random pointer using map.
Time Complexity : O(n)

In this program, we will use two functions as follows:

• cloneBinaryTree : Creates a duplicate tree where random pointer of every node is set to NULL. It populates the mapping between original and duplicate node.
• populateRandomPointer : It populate the random pointer in nodes of duplicate tree.

## C program to clone a binary tree with random pointer

```#include <stdio.h>
#include <limits.h>

struct node {
int data;
struct node *left;
struct node *right;
struct node *random;
};

struct mapPair {
struct node *key;
struct node *value;
};

struct mapPair map[100];
int mapSize = -1;

void putInIMap(struct node *key, struct node *value) {
mapSize++;
map[mapSize].key = key;
map[mapSize].value = value;
}

struct node* getValueFromMap(struct node *key) {
int i;
for(i = 0; i < mapSize; i++){
if(map[i].key == key)
return map[i].value;
}

return NULL;
}

struct node* getKeyFromMap(struct node *value) {
int i;
for(i = 0; i < mapSize; i++){
if(map[i].value == value)
return map[i].key;
}

return NULL;
}

struct node* getNewNode(int data) {
/* dynamically allocate memory for a new node */
struct node* newNode = (struct node*)malloc(sizeof(struct node));

/* populate data in new Node */
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
newNode->random = NULL;

return newNode;
}

/*
This function returns below tree
1
/ \
9    12
*/
struct node* generateBTree(){
// Root Node
struct node* root =  getNewNode(1);
// Level 2 nodes
root->left = getNewNode(9);
root->right = getNewNode(12);
// Populare random pointers
root->random = root->left;
root->left->random = root->right;
root->right->random = root->left;

return root;

}

/* Returns a tree which is exact copy of passed tree */
struct node* cloneBinaryTree(struct node *root){
if(root == NULL)
return NULL;
/* create a copy of root node */
struct node* newNode = getNewNode(root->data);
/*Put the mapping corresponding nodes of
original and cloned tree in a Map */
putInIMap(newNode, root);
/* Recursively create clone of left and right sub tree */
newNode->left = cloneBinaryTree(root->left);
newNode->right = cloneBinaryTree(root->right);
/* Return root of cloned tree */
return newNode;
}

void populateRandomPointer(struct node *root){
if(root != NULL){
populateRandomPointer(root->left);
struct node* originalRoot = getValueFromMap(root);
root->random = getKeyFromMap(root->random);
populateRandomPointer(root->right);
}
}

/*
Prints inOrder Traversal of a binary tree
*/
void inOrderTraversal(struct node *nodeptr){
if(nodeptr != NULL){
/* First, recursively prints in Order traversal of left sub-tree */
inOrderTraversal(nodeptr->left);
/* Prints current node */
printf("%d ", nodeptr->data);
/* Recursively prints in Order traversal of right sub-tree */
inOrderTraversal(nodeptr->right);
}
}
int main() {
struct node *clone, *root = generateBTree();

/*InOrder traversal of original tree */
printf("Original Tree\n");
inOrderTraversal(root);

clone = cloneBinaryTree(root);

/*InOrder traversal of clone tree */
printf("\nClone Tree\n");
inOrderTraversal(clone);
populateRandomPointer(clone);

getchar();
return 0;
}
```
Output
```Original
9 1 12
Clone Tree
9 1 12
```