Clone a Binary Tree with Random Pointers - GeeksforGeeks

Given a Binary Tree where every node has following structure.

struct node {  
    int key; 
    struct node *left,*right,*random;
} 

The random pointer points to any random node of the binary tree and can even point to NULL, clone the given binary tree.

Method 1 (Use Hashing)
The idea is to store mapping from given tree nodes to clone tre node in hashtable. Following are detailed steps.

1) Recursively traverse the given Binary and copy key value, left pointer and right pointer to clone tree. While copying, store the mapping from given tree node to clone tree node in a hashtable. In the following pseudo code, ‘cloneNode’ is currently visited node of clone tree and ‘treeNode’ is currently visited node of given tree.

   cloneNode->key  = treeNode->key
   cloneNode->left = treeNode->left
   cloneNode->right = treeNode->right
   map[treeNode] = cloneNode 

2) Recursively traverse both trees and set random pointers using entries from hash table.

   cloneNode->random = map[treeNode->random]

// This function creates clone by copying key and left and right pointers

// This function also stores mapping from given tree node to clone.

Node* copyLeftRightNode(Node* treeNode, map<Node *, Node *> *mymap)

{

    if (treeNode == NULL)

        return NULL;

    Node* cloneNode = newNode(treeNode->key);

    (*mymap)[treeNode] = cloneNode;

    cloneNode->left  = copyLeftRightNode(treeNode->left, mymap);

    cloneNode->right = copyLeftRightNode(treeNode->right, mymap);

    return cloneNode;

}

// This function copies random node by using the hashmap built by

// copyLeftRightNode()

void copyRandom(Node* treeNode,  Node* cloneNode, map<Node *, Node *> *mymap)

{

    if (cloneNode == NULL)

        return;

    cloneNode->random =  (*mymap)[treeNode->random];

    copyRandom(treeNode->left, cloneNode->left, mymap);

    copyRandom(treeNode->right, cloneNode->right, mymap);

}

// This function makes the clone of given tree. It mainly uses

// copyLeftRightNode() and copyRandom()

Node* cloneTree(Node* tree)

{

    if (tree == NULL)

        return NULL;

    map<Node *, Node *> *mymap = new  map<Node *, Node *>;

    Node* newTree = copyLeftRightNode(tree, mymap);

    copyRandom(tree, newTree, mymap);

    return newTree;

}

Method 2 (Temporarily Modify the Given Binary Tree)

1. Create a Clone Tree by copying left and right pointers (ignore random pointers).

2. For all nodes having a random pointer in given tree, store random of tree node in random of clone tree node. And link every clone tree node with given tree node using random pointers in given tree. Let ‘cloneNode’ be the currently visited node in clone tree and ‘treeNode’ be the currently visited node in given tree.

       cloneNode->random = treeNode->random; 
       treeNode->random  = cloneNode; 

3. Set the all the non-null random pointer in both given and clone trees properly

   i.e. cloneNode->random = cloneNode->random->random
        treeNode->random  = treeNode->random->random 

4. Set null random pointers in given tree properly (null random pointers in clone tree are already set correctly)

   i.e. if (clonenode->random == null) treenode->random = null 

// This function makes clone of given tree using left and right

// nodes only (ignore random nodes)

Node* copyLeftRightNode(Node* treeNode)

{

    if (treeNode == NULL)

        return NULL;

    Node* cloneNode = newNode(treeNode->key);

    cloneNode->left = copyLeftRightNode(treeNode->left);

    cloneNode->right = copyLeftRightNode(treeNode->right);

    return cloneNode;

}

// This function readjust random pointers.

void copyRandomNode(Node* treeNode, Node* cloneNode)

{

    if (treeNode == NULL)

        return;

    cloneNode->random = treeNode->random;

    treeNode->random = cloneNode;

    copyRandomNode(treeNode->left, cloneNode->left);

    copyRandomNode(treeNode->right, cloneNode->right);

}

//This function restores the non null random node for given both tree

void restoreTreeNullRandomNode(Node* treeNode, Node* cloneNode)

{

    if (treeNode == NULL)

        return;

    if (cloneNode->random == NULL)

        treeNode->random = NULL;

    restoreTreeNullRandomNode(treeNode->left, cloneNode->left);

    restoreTreeNullRandomNode(treeNode->right, cloneNode->right);

}

// This function restores the null random node for given  tree

// (random pointers of clone tree are already set correctly)

void restoreTreeNonNullRandomNode(Node* treeNode, Node* cloneNode)

{

    if (treeNode == NULL)

        return;

    if (treeNode->random != NULL && cloneNode->random != NULL)

    {

        Node* treeRandom = treeNode->random->random;

        Node* cloneRandom = cloneNode->random->random;

        restoreTreeNonNullRandomNode(treeNode->left, cloneNode->left);

        restoreTreeNonNullRandomNode(treeNode->right, cloneNode->right);

        treeNode->random =  treeRandom;

        cloneNode->random = cloneRandom;

    }

    else

    {

        restoreTreeNonNullRandomNode(treeNode->left, cloneNode->left);

        restoreTreeNonNullRandomNode(treeNode->right, cloneNode->right);

    }

}

//This function makes the clone of given tree

Node* cloneTree(Node* treeNode)

{

    if (treeNode == NULL)

        return NULL;

    Node* cloneNode = copyLeftRightNode(treeNode);

    copyRandomNode(treeNode, cloneNode);

    restoreTreeNonNullRandomNode(treeNode, cloneNode);

    restoreTreeNullRandomNode(treeNode, cloneNode);

    return cloneNode;

}

Extension
Reverse linked list with arbit / random pointer using constant spaceRead full article from Clone a Binary Tree with Random Pointers - GeeksforGeeks