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
Posted by
Labels: