Table of Contents
Problem Statement
You are given a complete binary tree with some random pointers. Random pointers are referred to nodes which every node points to other than its left and right child. So, this also changes the standard structure of a node in a simple binary tree. Now the node of a binary tree will store the data at the current node and pointer to left, right, and random pointer. So, now we are good to go with what does the problem even ask? The problem “Clone a binary tree with random pointers” asks to create a new binary tree which is an exact copy of the given initial tree. So in the new created tree, if we pick a node its left, right, and random pointer refers to the nodes in this new tree which are corresponding to the nodes in the original tree.
Example
Input
Inorder traversal of original binary tree is [current node data, random pointer data]: [1 2], [2 7], [3 9], [5 1], [7 1], [9 5], Inorder traversal of cloned binary tree is[current node data, random pointer data]: [1 2], [2 7], [3 9], [5 1], [7 1], [9 5],
Explanation
The left and right nodes of binary tree are shown as usual on the left and right of each node. And all the pointers others the left and right pointers are random pointers. Some edges have double arrows (that is pointing in both directions). The direction to any of the parents of the node denotes that node has a random pointer to parent. The output is given in [current node data/ random node data] format.
Hashing Approach
So, as we know that we need to create a new tree which is an exact copy of the initial tree. We can run an inorder traversal and construct a copy. But we will face problems with random pointers because some nodes may be pointing to nodes which are not constructed yet. So to get rid of this error. We will first construct a new tree. Then use a HashMap which stores the address of the new node corresponding to each node in the original tree. So once again we run an inorder traversal and make the random pointers to the nodes of the new tree (which are stored as values in HashMap).
Efficient Approach
In the approach above, we had to keep a HashMap which stored a clone node address corresponding to each node in the original tree. So instead of doing that, we will do something as done to clone a linked list with random pointers. We will push the newly created nodes between the left child and the corresponding node in the original tree. So until now, we have changed the structure of the initial tree. To set random pointers we know that a new node corresponding to a node is always its left child. Thus we simply set the random pointer to the left child of the node in the input tree. But still we have one thing to care of. We need to restore the left child of nodes of the initial & clone tree. Once that’s done we have cloned a binary tree with random poinṭers.
Code
C++ code to Clone a Binary Tree with Random Pointers
#include <iostream>
using namespace std;
struct node{
int data;
node *left, *right, *random;
};
node* create(int data){
node* tmp = new node();
tmp->data = data;
tmp->left = tmp->right = tmp->random = NULL;
}
// print inorder traversal of the given tree in [node, random node] format
void inorder(node* root)
{
if(root == NULL)
return;
// print inorder traversal of left tree
inorder(root->left);
// print in [current node, random node] format
cout << "[" << root->data << " ";
if (root->random == NULL)
cout << "NULL], ";
else
cout << root->random->data << "], ";
// print inorder traversal of right tree
inorder(root->right);
}
// insert clone nodes between the original node and its left child
node* insertCloneNode(node* originalNode)
{
if (originalNode == NULL)
return NULL;
node* left = originalNode->left;
originalNode->left = create(originalNode->data);
originalNode->left->left = left;
if(left != NULL)
left->left = insertCloneNode(left);
originalNode->left->right = insertCloneNode(originalNode->right);
return originalNode->left;
}
// sets the random pointers in clone tree
void setRandomNode(node* originalNode, node* cloneNode)
{
if (originalNode == NULL)
return;
if(originalNode->random != NULL)
cloneNode->random = originalNode->random->left;
else
cloneNode->random = NULL;
if(originalNode->left != NULL && cloneNode->left != NULL)
setRandomNode(originalNode->left->left, cloneNode->left->left);
setRandomNode(originalNode->right, cloneNode->right);
}
// after all the work restore the left pointers in original and clone tree
void restoreTreeLeftNode(node* originalNode, node* cloneNode)
{
if (originalNode == NULL)
return;
if (cloneNode->left != NULL)
{
node* cloneLeft = cloneNode->left->left;
originalNode->left = originalNode->left->left;
cloneNode->left = cloneLeft;
}
else
originalNode->left = NULL;
restoreTreeLeftNode(originalNode->left, cloneNode->left);
restoreTreeLeftNode(originalNode->right, cloneNode->right);
}
// constructs the new clone tree
node* cloneTree(node* originalNode)
{
if (originalNode == NULL)
return NULL;
node* cloneNode = insertCloneNode(originalNode);
setRandomNode(originalNode, cloneNode);
restoreTreeLeftNode(originalNode, cloneNode);
return cloneNode;
}
int main()
{
node *root = create(3);
node* two = create(2);
node* one = create(1);
node* seven = create(7);
node* five = create(5);
node* nine = create(9);
root->left = two;
root->left->left = one;
root->right = seven;
root->right->left = five;
root->right ->right = nine;
root->random = nine;
root->left->random = seven;
root->left->left->random = two;
root->right->random = one;
root->right->left->random = one;
root->right->right->random = five;
cout << "Inorder traversal of original binary tree is [current node data, random pointer data]: \n";
inorder(root);
node *clone = cloneTree(root);
cout << "\n\nInorder traversal of cloned binary tree is[current node data, random pointer data]: \n";
inorder(clone);
return 0;
}
Inorder traversal of original binary tree is [current node data, random pointer data]: [1 2], [2 7], [3 9], [5 1], [7 1], [9 5], Inorder traversal of cloned binary tree is[current node data, random pointer data]: [1 2], [2 7], [3 9], [5 1], [7 1], [9 5],
Java code to Clone a Binary Tree with Random Pointers
import java.util.*;
// Class that denotes a node of the tree
class node
{
int data;
node left, right, random;
public node(int data)
{
this.data = data;
left = right = random = null;
}
}
class Tree
{
static node root;
static node create(int data) {
node tmp = new node(data);
return tmp;
}
// print inorder traversal of the given tree in [node, random node] format
static void inorder(node root){
if(root != null){
// print inorder traversal of left tree
inorder(root.left);
// print in [current node, random node] format
System.out.print("[" + root.data + " ");
if(root.random == null)
System.out.print("null], ");
else
System.out.print(root.random.data +"], ");
// print inorder traversal of right tree
inorder(root.right);
}
}
// insert clone nodes between the original node and its left child
static node insertCloneNode(node originalNode)
{
if (originalNode == null)
return null;
node left = originalNode.left;
originalNode.left = create(originalNode.data);
originalNode.left.left = left;
if(left != null)
left.left = insertCloneNode(left);
originalNode.left.right = insertCloneNode(originalNode.right);
return originalNode.left;
}
// sets the random pointers in clone tree
static void setRandomNode(node originalNode, node cloneNode)
{
if (originalNode != null){
if(originalNode.random != null)
cloneNode.random = originalNode.random.left;
else
cloneNode.random = null;
if(originalNode.left != null && cloneNode.left != null)
setRandomNode(originalNode.left.left, cloneNode.left.left);
setRandomNode(originalNode.right, cloneNode.right);
}
}
// after all the work restore the left pointers in original and clone tree
static void restoreTreeLeftNode(node originalNode, node cloneNode)
{
if (originalNode != null) {
if (cloneNode.left != null)
{
node cloneLeft = cloneNode.left.left;
originalNode.left = originalNode.left.left;
cloneNode.left = cloneLeft;
}
else
originalNode.left = null;
restoreTreeLeftNode(originalNode.left, cloneNode.left);
restoreTreeLeftNode(originalNode.right, cloneNode.right);
}
}
// constructs the new clone tree
static node cloneTree(node originalNode)
{
if (originalNode == null)
return null;
node cloneNode = insertCloneNode(originalNode);
setRandomNode(originalNode, cloneNode);
restoreTreeLeftNode(originalNode, cloneNode);
return cloneNode;
}
public static void main(String[] args) {
node root = create(3);
node two = create(2);
node one = create(1);
node seven = create(7);
node five = create(5);
node nine = create(9);
root.left = two;
root.left.left = one;
root.right = seven;
root.right.left = five;
root.right .right = nine;
root.random = nine;
root.left.random = seven;
root.left.left.random = two;
root.right.random = one;
root.right.left.random = one;
root.right.right.random = five;
System.out.print("Inorder traversal of original binary tree is[current node data, random pointer data]: \n");
inorder(root);
node clone = cloneTree(root);
System.out.print("\n\nInorder traversal of cloned binary tree is[current node data, random pointer data]: \n");
inorder(clone);
}
}Inorder traversal of original binary tree is[current node data, random pointer data]: [1 2], [2 7], [3 9], [5 1], [7 1], [9 5], Inorder traversal of cloned binary tree is[current node data, random pointer data]: [1 2], [2 7], [3 9], [5 1], [7 1], [9 5],
Complexity Analysis to Clone a Binary Tree with Random Pointers
Time Complexity
O(N), we have just traversed the nodes in the binary tree, and since there are N nodes in binary tree. Thus the time complexity is linear.
Space Complexity
O(1), as we have not stored any information in array or map. Thus the space complexity is constant.