- 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