Clone a Binary Tree with Random Pointers

Examples

Input 1:

Output 1:

[1 NULL], [2 3], [4 NULL], [5 4]. [3 NULL], [6 2],

Input 2:

Output 2:

[1 NULL], [2 3], [3 NULL], [4 2], [5 4],

Approach 1(Using Hashing)

Approach 1 uses hashing to achieve the solution. In this, we travel the whole tree and store the mapping from the given tree nodes to every clone tree node. We have discussed the step-by-step process to do so in the algorithm section below:

Algorithm

1. Travel the original binary tree recursively while traversing copy data, the left pointer, and the right pointer to the cloned tree.
2. During copying store, the store the mapping relation from given tree to clone tree in a hash table. In the code given below the CopyBinaryTree() function is performing this operation
3. After copying the left and right pointers, it is time to copy and set the reference of the random pointer.
4. Travel in the tree recursively and set the random pointer with the entries in the hash table.
5. Now print the preorder with random pointers of the original and copied tree. They must be the same. The code of the same is given below:

Code in C++

#include<bits/stdc++.h>
using namespace std;
struct Tree{
int data;
Tree* left,*right,*random;
Tree(int data){
    this->data=data;
    this->right=this->left=NULL;
    this->random=NULL;
}
};

 
//Here, we will map all the left and right nodes of all the nodes
// So that we can use them for copy
Tree* CopyBinaryTree(Tree* treeNode, unordered_map<Tree *, Tree *> &mp)
{
    if (treeNode == NULL)
        return NULL;
    Tree* cloneNode = new Tree(treeNode->data);
    mp[treeNode] = cloneNode;
    cloneNode->left  = CopyBinaryTree(treeNode->left, mp);
    cloneNode->right = CopyBinaryTree(treeNode->right, mp);
    return cloneNode;
}
 
// In this function we only copy the random pointer
// As the copyBinaryTree() function has already mapped the left and right nodes of the bianry tree
void CopyRandomNodes(Tree * treeNode,  Tree* cloneNode, unordered_map<Tree *, Tree *> &mp)
{
    if (cloneNode == NULL)
        return;
    cloneNode->random =  mp[treeNode->random];
    CopyRandomNodes(treeNode->left, cloneNode->left, mp);
    CopyRandomNodes(treeNode->right, cloneNode->right, mp);
}
 
// This function makes the clone of given tree. It mainly uses
// CopyBinaryTree() and CopyRandomNodes()
Tree* deepclonetree(Tree* root)
{
    if (root == NULL)
        return root;
    unordered_map<Tree *, Tree *> mp;
    // first we map the left and right subtree
    Tree* sample_tree = CopyBinaryTree(root, mp);
    //After mapping the left and right subtree we will copy and map the random pointers
    CopyRandomNodes(root, sample_tree, mp);
    return sample_tree;
}
 
void preorder(Tree*root){
    if (root == nullptr) {
        return;
    }
    cout << "[" << root->data << " ";
    if (root->random != NULL)
    cout << root->random->data << "], ";
    else
        cout << "NULL], ";
        preorder(root->left);
        preorder(root->right);
}
int main(){
    Tree *root=new Tree(6);
 root->left = new Tree(8);
    root->right = new Tree(4);
    root->left->left = new Tree(1);
    root->left->right = new Tree(2);
    root->right->left=new Tree(0);
    root->right->right = new Tree(7);
 root->left->right->random=root->left->left;
 root->right->right->random=root->left;
 root->left->random=root->right;
   
 cout<<"The Preorder travesal of original binary tree is : "<<endl;
    preorder(root);
    cout<<endl;
    Tree *cloneNode = deepclonetree(root);
    cout<<"The preorder travesal of clonned tree is : ";
    cout<<endl;
        preorder(cloneNode);
}

Output:

The Preorder travesal of original binary tree is :
[6 NULL], [8 4], [1 NULL], [2 1], [4 NULL], [0 NULL], [7 8],
The preorder travesal of clonned tree is :
[6 NULL], [8 4], [1 NULL], [2 1], [4 NULL], [0 NULL], [7 8],

Time Complexity: O(N)

Here we are traversing the tree two or three times, so this will give the overall time complexity of O(N).

Space Complexity: O(N)

Since we are using an unordered_map that stores the relation between the original and cloned tree and stores every node in the given tree, this will contribute to the extra space of O(N).

Approach 2 (Modifying original Binary Tree Temporarily)

In this approach, we will slightly modify the original binary tree. We will add similar nodes in the binary tree and then receive our cloned tree. We have discussed the step-by-step explanation of this approach in the algorithm section below:

Algorithm

1. We will travel in the whole tree, and for every node, we will make a new node of the same value for the cloned tree and insert it between the original node and its left pointer in the original tree.
2. Suppose you have a node with a value X, and at the left of X, you have Y, so let's suppose the cloned X node is xX so that xX will be between X and Y.
3. The right child pointer will be set in the original state like for node X, and its right child Y, the corresponding cloned nodes will be xX and yY.
4. Then like Y is the right child of X in the same way, yY will be the right child of xX.
5. After changing the left and right pointers, we will change the random pointers. W will set the random pointers in the same order as the original tree.
6. At last, restore the left pointer of cloned and original binary tree correctly.

Code in C++

#include<bits/stdc++.h>
using namespace std;
struct Tree{
int data;
Tree* left,*right,*random;
Tree(int data){
    this->data=data;
    this->right=this->left=NULL;
    this->random=NULL;
}
};
 
// Print Preorder of the binary tree
void preorder(Tree*root){
    if (root == nullptr) {
        return;
    }
    cout << "[" << root->data << " ";
    if (root->random != NULL)
    cout << root->random->data << "], ";
    else
        cout << "NULL], ";
        preorder(root->left);
        preorder(root->right);
}
 
// We will create a copy of the current node and insert it between its left node and its current position
Tree* copyBinaryTree(Tree* root)
{
    if (root == NULL)
        return NULL;
 
    Tree* left = root->left;
    root->left = new Tree(root->data);
    root->left->left = left;

 
    if(left != NULL)
        left->left = copyBinaryTree(left);
 
    root->left->right = copyBinaryTree(root->right);
    return root->left;
}
 
// This function will take care of the random pointers in the tree.
// Like if a random pointer of A is pointing to B in an original tree
// Then copied A will point to copied B in the clone Tree
void CloneRandomNodes(Tree* root, Tree* ClonnedNode)
{
    if (root == NULL)
        return;
    if(root->random != NULL)
        ClonnedNode->random = root->random->left;
    else
        ClonnedNode->random = NULL;
 
    if(root->left != NULL && ClonnedNode->left != NULL)
        CloneRandomNodes(root->left->left, ClonnedNode->left->left);
    CloneRandomNodes(root->right, ClonnedNode->right);
}
 
// This function will restore left pointers correctly in
// both original and cloned tree
void restoreTreeLeftNode(Tree* root, Tree* ClonnedNode)
{
    if (root == NULL)
        return;
    if (ClonnedNode->left != NULL)
    {
        Tree* cloneLeft = ClonnedNode->left->left;
        root->left = root->left->left;
        ClonnedNode->left = cloneLeft;
    }
    else
        root->left = NULL;
 
    restoreTreeLeftNode(root->left, ClonnedNode->left);
    restoreTreeLeftNode(root->right, ClonnedNode->right);
}
 
//This function makes the clone of the given tree
Tree* deepclonetree(Tree* root)
{
    if (root == NULL)
        return root;
    Tree* ClonnedNode = copyBinaryTree(root);
    CloneRandomNodes(root, ClonnedNode);
    restoreTreeLeftNode(root, ClonnedNode);
    return ClonnedNode;
}

 
int main(){
    Tree *root=new Tree(6);
 root->left = new Tree(8);
    root->right = new Tree(4);
    root->left->left = new Tree(1);
    root->left->right = new Tree(2);
    root->right->left=new Tree(0);
    root->right->right = new Tree(7);
 root->left->right->random=root->left->left;
 root->right->right->random=root->left;
 root->left->random=root->right;
    cout<<"The Preorder traversal of original binary tree is : "<<endl;
    preorder(root);
    cout<<endl;
    Tree *ClonnedNode = deepclonetree(root);
    cout<<"The preorder travesal of clonned tree is : ";
    cout<<endl;
        preorder(ClonnedNode);
}

Output:

The Preorder travesal of original binary tree is :
[6 NULL], [8 4], [1 NULL], [2 1], [4 NULL], [0 NULL], [7 8],
The preorder travesal of clonned tree is :
[6 NULL], [8 4], [1 NULL], [2 1], [4 NULL], [0 NULL], [7 8],

Time Complexity: O(N)

Here we are traversing the tree two or three times, so this will give the overall time complexity of O(N).

Space Complexity: O(N)

Here we are returning a new tree with the exact same number of nodes as the original, which will contribute to a space complexity of O(N).

Frequently Asked Questions

What do you understand by root node in a binary tree?

Root Node is the top most or first node in the binary tree.

What is the difference between a binary search tree and a binary tree?

The main difference between a binary search tree and the binary tree is that in a binary search tree, all the nodes smaller than the parent nodes are on the left side of the parent node. All the greater nodes than the parent node will be on the right side of the parent node, whereas they can be randomly arranged in the case of the binary tree.

What is the time complexity of hashing?

The overall time complexity of the hash function is O(1).

What is a Complete Binary tree?

The complete binary tree is the tree that is fully filled except for the last level, and the last level has been filled from the left.

In the above question, can random always need to point to a node in the tree?

No, the random pointer must not always point to a node in the tree. If it does not point to any node, it will equal NULL.

Conclusion

In this article, we have discussed one of the most asked questions of binary trees in the interview Clone binary tree with random pointers. We have explained the problem in detail, solved it using two approaches, and discussed their code and complexities.

If you are not comfortable with binary trees and want to have a quick overview, then have a look at this blog there. You will get a complete overview of the Binary Tree. You can always trust our paid courses for the best quality content.
Check out this problem - Largest BST In Binary Tree

Do upvote our blogs if you find them helpful and engaging!

 “Happy Coding!”