Clone a Binary Tree with Random Pointers
Given a Binary Tree where every node has the 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 a mapping from given tree nodes to clone tree nodes in the hashtable. Following are detailed steps.
1) Recursively traverse the given Binary and copy key-value, left pointer, and a right pointer to clone tree. While copying, store the mapping from the given tree node to clone the tree node in a hashtable. In the following pseudo-code, ācloneNodeā is the currently visited node of the clone tree and ātreeNodeā is the currently visited node of the 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 the hash table.
cloneNode->random = map[treeNode->random]
Following are the C++ and Java implementation of above idea. The following implementation uses unordered_map from C++ STL and HashMap in Java. Note that the map doesnāt implement a hash table, it actually is based on a self-balancing binary search tree.
Implementation:
CPP
// A hashmap based C++ program to clone a binary // tree with random pointers #include<iostream> #include<unordered_map> using namespace std; /* A binary tree node has data, pointer to left child, a pointer to right child and a pointer to random node*/ struct Node { int key; struct Node* left, *right, *random; }; /* Helper function that allocates a new Node with the given data and NULL left, right and random pointers. */ Node* newNode( int key) { Node* temp = new Node; temp->key = key; temp->random = temp->right = temp->left = NULL; return (temp); } /* Given a binary tree, print its Nodes in inorder*/ void printInorder(Node* node) { if (node == NULL) return ; /* First recur on left subtree */ printInorder(node->left); /* then print data of Node and its random */ cout << "[" << node->key << " " ; if (node->random == NULL) cout << "NULL], " ; else cout << node->random->key << "], " ; /* now recur on right subtree */ printInorder(node->right); } /* 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, unordered_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, unordered_map<Node *, Node *> &mymap) { if (treeNode == NULL) return ; mymap[treeNode]->random = mymap[treeNode->random]; copyRandom(treeNode->left, mymap); copyRandom(treeNode->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; unordered_map<Node *, Node *> mymap; Node* newTree = copyLeftRightNode(tree, mymap); copyRandom(tree, mymap); return newTree; } /* Driver program to test above functions*/ int main() { //Test No 1 Node *tree = newNode(1); tree->left = newNode(2); tree->right = newNode(3); tree->left->left = newNode(4); tree->left->right = newNode(5); tree->random = tree->left->right; tree->left->left->random = tree; tree->left->right->random = tree->right; // Test No 2 // tree = NULL; // Test No 3 // tree = newNode(1); // Test No 4 /* tree = newNode(1); tree->left = newNode(2); tree->right = newNode(3); tree->random = tree->right; tree->left->random = tree; */ cout << "Inorder traversal of original binary tree is: \n" ; printInorder(tree); Node *clone = cloneTree(tree); cout << "\n\nInorder traversal of cloned binary tree is: \n" ; printInorder(clone); return 0; } //This code was modified by Rohit Iyer(rohit_iyer) |
Java
import java.lang.*; import java.util.*; class Tree { int data; Tree left, right, random; Tree( int d) { data = d; left = null ; right = null ; random = null ; } } class CloneABT { public static void main(String[] args) { Tree tree = new Tree( 1 ); tree.left = new Tree( 2 ); tree.right = new Tree( 3 ); tree.left.left = new Tree( 4 ); tree.left.right = new Tree( 5 ); tree.random = tree.left.right; tree.left.left.random = tree; tree.left.right.random = tree.right; System.out.println( "Inorder traversal of original binary tree is: \n" ); printInorder(tree); Tree clone = cloneTree(tree); System.out.println( "\n\nInorder traversal of cloned binary tree is: \n" ); printInorder(clone); } public static Tree cloneTree(Tree tree) { if (tree == null ) return null ; HashMap<Tree, Tree> map = new HashMap<>(); // create a hashmap to store // the randoms Tree newtree = clonelr(tree, map); copyrandom(tree, newtree, map); return newtree; } // cloning the left and right tree public static Tree clonelr(Tree tree, HashMap<Tree, Tree> map) { if (tree == null ) return null ; Tree clonenode = new Tree(tree.data); map.put(tree, clonenode); clonenode.left = clonelr(tree.left, map); clonenode.right = clonelr(tree.right, map); return clonenode; } // setting the random pointers in the cloned tree public static void copyrandom(Tree tree, Tree clone, HashMap<Tree, Tree> map) { if (clone == null ) return ; clone.random = map.get(tree.random); copyrandom(tree.left, clone.left, map); copyrandom(tree.right, clone.right, map); } static void printInorder(Tree node) { if (node == null ) return ; /* First recur on left subtree */ printInorder(node.left); /* then print data of Node and its random */ System.out.print( "[" + node.data + " " ); if (node.random == null ) System.out.print( "null], " ); else System.out.print(node.data + "]" ); /* now recur on right subtree */ printInorder(node.right); } public static boolean printInorder(Tree a, Tree b) { if ((a == null ) && (b == null )) return true ; if (a != null && b != null ) { boolean check = ((a.data == b.data) && printInorder(a.left, b.left) && printInorder(a.right, b.right)); if (a.random != null && b.random != null ) return ( check && (a.random.data == b.random.data)); if (a.random == b.random) return check; return false ; } return false ; } public static void clone(Tree root, Tree proot, int n1, int n2) { try { if (root == null && proot == null ) return ; if (n1 == root.data) { if (proot.data == n2) root.random = proot; else { clone(root, proot.left, n1, n2); clone(root, proot.right, n1, n2); } } else { clone(root.left, proot, n1, n2); clone(root.right, proot, n1, n2); } } catch (NullPointerException ex) { } } public static void insert(Tree root, int n1, int n2, char lr) { if (root == null ) return ; if (n1 == root.data) { switch (lr) { case 'L' : root.left = new Tree(n2); break ; case 'R' : root.right = new Tree(n2); break ; } } else { insert(root.left, n1, n2, lr); insert(root.right, n1, n2, lr); } } } |
Python3
# A hashmap based Python program to clone a binary # tree with random pointers class Node: def __init__( self , key): self .key = key self .left = None self .right = None self .random = None # Helper function that allocates a new Node with the # given data and None left, right and random pointers. def new_node(key): temp = Node(key) return temp # Given a binary tree, print its Nodes in inorder def print_inorder(node): if node = = None : return # First recur on left subtree print_inorder(node.left) # then print data of Node and its random print ( "[" , node.key, end = ", " ) if node.random = = None : print ( "None], " , end = "") else : print (node.random.key, "], " , end = "") # now recur on right subtree print_inorder(node.right) # This function creates clone by copying key # and left and right pointers. This function also # stores mapping from given tree node to clone. def copy_left_right_node(tree_node, mymap): if tree_node = = None : return None clone_node = new_node(tree_node.key) mymap[tree_node] = clone_node clone_node.left = copy_left_right_node(tree_node.left, mymap) clone_node.right = copy_left_right_node(tree_node.right, mymap) return clone_node # This function copies random node by using the hashmap built by # copy_left_right_node() def copy_random(tree_node, mymap): if tree_node is None : return if tree_node.random is not None : mymap[tree_node].random = mymap[tree_node.random] copy_random(tree_node.left, mymap) copy_random(tree_node.right, mymap) # This function makes the clone of given tree. It mainly uses # copy_left_right_node() and copy_random() def clone_tree(tree): if tree = = None : return None mymap = {} new_tree = copy_left_right_node(tree, mymap) copy_random(tree, mymap) return new_tree # Driver code if __name__ = = "__main__" : # Test Case 1 tree = Node( 1 ) tree.left = Node( 2 ) tree.right = Node( 3 ) tree.left.left = Node( 4 ) tree.left.right = Node( 5 ) tree.random = tree.left.right tree.left.left.random = tree tree.left.right.random = tree.right # Test Case 2 # tree = None # Test Case 3 # tree = newNode(1) # Test Case 4 """ tree = newNode(1) tree.left = newNode(2) tree.right = newNode(3) tree.random = tree.right tree.left.random = tree """ print ( "Inorder traversal of original binary tree is:" ) print_inorder(tree) clone = clone_tree(tree) print ( "\n\nInorder traversal of cloned binary tree is:" ) print_inorder(clone) |
C#
// C# Program for the above approach using System; using System.Collections.Generic; namespace BinaryTreeWithRandomPointers { class Node { public int key; public Node left, right, random; public Node( int item) { key = item; left = right = random = null ; } } class Program { static void Main( string [] args) { // Test Case 1 Node tree = new Node(1); tree.left = new Node(2); tree.right = new Node(3); tree.left.left = new Node(4); tree.left.right = new Node(5); tree.random = tree.left.right; tree.left.left.random = tree; tree.left.right.random = tree.right; // Test Case 2 // Node tree = null; // Test Case 3 // Node tree = new Node(1); // Test Case 4 /* Node tree = new Node(1); tree.left = new Node(2); tree.right = new Node(3); tree.random = tree.right; tree.left.random = tree; */ Console.WriteLine( "Inorder traversal of original binary tree is:" ); PrintInorder(tree); Node clone = CloneTree(tree); Console.WriteLine( "\n\nInorder traversal of cloned binary tree is:" ); PrintInorder(clone); } // Given a binary tree, print its Nodes in inorder static void PrintInorder(Node node) { if (node == null ) { return ; } // First recur on left subtree PrintInorder(node.left); // then print data of Node and its random Console.Write( "[" + node.key + ", " ); if (node.random == null ) { Console.Write( "None], " ); } else { Console.Write(node.random.key + "], " ); } // now recur on right subtree PrintInorder(node.right); } // This function creates clone by copying key // and left and right pointers. This function also // stores mapping from given tree node to clone. static Node CopyLeftRightNode(Node treeNode, Dictionary<Node, Node> mymap) { if (treeNode == null ) { return null ; } Node cloneNode = new Node(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() static void CopyRandom(Node treeNode, Dictionary<Node, Node> mymap) { if (treeNode == null ) { return ; } if (treeNode.random != null ) { mymap[treeNode].random = mymap[treeNode.random]; } CopyRandom(treeNode.left, mymap); CopyRandom(treeNode.right, mymap); } // This function makes the clone of given tree. It mainly uses // CopyLeftRightNode() and CopyRandom() static Node CloneTree(Node tree) { if (tree == null ) { return null ; } Dictionary<Node, Node> mymap = new Dictionary<Node, Node>(); Node newTree = CopyLeftRightNode(tree, mymap); CopyRandom(tree, mymap); return newTree; } } } // This code is contributed by codebraxnzt |
Javascript
class Node { constructor(key) { this .key = key; this .left = null ; this .right = null ; this .random = null ; } } function newNode(key) { let temp = new Node(key); return temp; } function printInorder(node) { if (node == null ) { return ; } printInorder(node.left); console.log( "[" , node.key, ", " , node.random ? node.random.key : 'None' , "], " ); printInorder(node.right); } function copyLeftRightNode(treeNode, mymap) { if (treeNode == null ) { return null ; } let cloneNode = newNode(treeNode.key); mymap[treeNode] = cloneNode; cloneNode.left = copyLeftRightNode(treeNode.left, mymap); cloneNode.right = copyLeftRightNode(treeNode.right, mymap); return cloneNode; } function copyRandom(treeNode, mymap) { if (treeNode == null ) { return ; } if (treeNode.random !== null ) { mymap[treeNode].random = mymap[treeNode.random]; } copyRandom(treeNode.left, mymap); copyRandom(treeNode.right, mymap); } function cloneTree(tree) { if (tree == null ) { return null ; } let mymap = {}; let newTree = copyLeftRightNode(tree, mymap); copyRandom(tree, mymap); return newTree; } // Test Case 1 let tree = new Node(1); tree.left = new Node(2); tree.right = new Node(3); tree.left.left = new Node(4); tree.left.right = new Node(5); tree.random = tree.left.right; tree.left.left.random = tree; tree.left.right.random = tree.right; // Test Case 2 // tree = null; // Test Case 3 // tree = newNode(1); // Test Case 4 /* tree = newNode(1); tree.left = newNode(2); tree.right = newNode(3); tree.random = tree.right; tree.left.random = tree; */ console.log( "Inorder traversal of original binary tree is:" ); let output = "" ; printInorder(tree); console.log(); console.log( "Inorder traversal of cloned binary tree is:" ); let clone = cloneTree(tree); printInorder(clone); console.log(); |
Inorder traversal of original binary tree is: [4 1], [2 NULL], [5 3], [1 5], [3 NULL], Inorder traversal of cloned binary tree is: [4 1], [2 NULL], [5 3], [1 5], [3 NULL],
Time complexity: O(n), this is because we need to traverse the entire tree in order to copy the left and right pointers, and then we need to traverse the tree again to copy the random pointers.
Auxiliary Space: O(n), this is because we need to store a mapping of the original treeās nodes to their clones.
Contact Us