Open In App

Clone a Binary Tree with Random Pointers

Last Updated : 27 Jun, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Given a Binary Tree where every node has the following structure. 

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

Binary tree with random pointers

Binary tree with random pointers

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

Recommended Practice

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();


Output

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.



Previous Article
Next Article

Similar Reads

Clone a Linked List with next and Random Pointer
Given a linked list of size N where each node has two links: one pointer points to the next node and the second pointer points to any node in the list. The task is to create a clone of this linked list in O(N) time. Note: The pointer pointing to the next node is 'next' pointer and the one pointing to an arbitrary node is called 'arbit' pointer as i
15+ min read
Clone a linked list with next and random pointer | Set 2
We have already discussed 2 different ways to clone a linked list. In this post, one more simple method to clone a linked list is discussed. Recommended PracticeClone a linked list with next and random pointerTry It! The idea is to use Hashing. Below is algorithm. Traverse the original linked list and make a copy in terms of data. Make a hash map o
11 min read
Clone a linked list with next and random pointer in O(1) space
Given a linked list having two pointers in each node. The first one points to the next node of the list, however, the other pointer is random and can point to any node of the list. Write a program that clones the given list in O(1) space, i.e., without any extra space. Examples: Input : Head of the below-linked list Output : A new linked list ident
10 min read
Modify a binary tree to get preorder traversal using right pointers only
Given a binary tree. Modify it in such a way that after modification you can have a preorder traversal of it using only the right pointers. During modification, you can use right as well as left pointers. Examples: Input : 10 / \ 8 2 / \ 3 5 Output : 10 \ 8 \ 3 \ 5 \ 2 Explanation : The preorder traversal of given binary tree is 10 8 3 5 2. Method
15 min read
Convert Binary Tree to Doubly Linked List by fixing left and right pointers
Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be the same as in Inorder for the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the
12 min read
Find right sibling of a binary tree with parent pointers
Given a binary tree with parent pointers, find the right sibling of a given node(pointer to the node will be given), if it doesn’t exist return null. Do it in O(1) space and O(n) time? Examples: 1 / \ 2 3 / \ \ 4 6 5 / \ \ 7 9 8 / \ 10 12 Input : Given above tree with parent pointer and node 10 Output : 12 Recommended: Please solve it on PRACTICE f
10 min read
Complexity of different operations in Binary tree, Binary Search Tree and AVL tree
In this article, we will discuss the complexity of different operations in binary trees including BST and AVL trees. Before understanding this article, you should have a basic idea about Binary Tree, Binary Search Tree, and AVL Tree. The main operations in a binary tree are: search, insert and delete. We will see the worst-case time complexity of t
4 min read
Convert a Binary Tree into its Mirror Tree (Invert Binary Tree)
Given a binary tree, the task is to convert the binary tree into its Mirror tree. Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged. Recommended PracticeMirror TreeTry It!The idea is to traverse recursively and swap the right and left subtrees after traversing the subtrees. Follow
15+ min read
Implement random-0-6-Generator using the given random-0-1-Generator
Given a function random01Generator() that gives you randomly either 0 or 1, implement a function that utilizes this function and generate numbers between 0 and 6(both inclusive). All numbers should have same probabilities of occurrence. Examples: on multiple runs, it gives 3 2 3 6 0 Approach : The idea here is to find the range of the smallest numb
5 min read
Test Case Generation | Set 2 ( Random Characters, Strings and Arrays of Random Strings)
Set 1 (Random Numbers, Arrays and Matrices) Generating Random Characters C/C++ Code // A C++ Program to generate test cases for // random characters #include&lt;bits/stdc++.h&gt; using namespace std; // Define the number of runs for the test data // generated #define RUN 5 // Define the range of the test data generated // Here it is 'a' to 'z' #def
11 min read
Article Tags :
Practice Tags :