Clone a Binary Tree with Random Pointers

Question

Can anyone explain the way of cloning the binary tree with random pointers apart from left to right? every node has following structure.

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

This is very popular interview question and I am able to figure out the solution based on hashing(which is similar to cloning of linked lists). I tried to understand the solution given in Link (approach 2) but am not able to figure out what does it want to convey by reading code also. I don't expect solution based on hashing as it is intuitive and pretty straight forward. Please explain solution based on modifying binary tree and cloning it.

Answer 1

The solution presented is based on the idea of interleaving both trees, the original one and its clone.

For every node A in the original tree, its clone cA is created and inserted as A's left child. The original left child of A is shifted one level down in the tree structure and becomes a left child of cA.

For each node B, which is a right child of its parent P (i.e., B == P->right), a pointer to its clone node cB is copied to a clone of its parent.

       P                     P
      / \                   / \
     /   \                 /   \
    A     B               cP    B
   /       \             / \   / \
  /         \           /   \ /   \
 X           Z         A    cB     Z
                      /       \   /
                     cA        cZ
                    /
                   X
                  /
                 cX

Finally we can extract the cloned tree by traversing the interleaved tree and unlinking every other node on each 'left' path (starting from root->left) together with its 'rightmost' descendants path and, recursively, every other 'left' descendant of those and so on.

What's important, each cloned node is a direct left child of its original node. So in the middle part of the algorithm, after inserting the cloned nodes but before extracting them, we can traverse the whole tree walking on original nodes, and whenever we find a random pointer, say A->random == Z, we can copy the binding into clones by setting cA->random = cZ, which resolves to something like

A->left->random = A->random->left;

This allows cloning random pointers directly and does not require additional hash maps (at the cost of interleaving new nodes into the original tree and extracting them later).

Answer 2

The interleaving method can be simplified a little, I think.

1) For every node A in the original tree, create clone cA with the same left and right pointers as A. Then, set As left pointer to cA.

       P                     P
      / \                   / 
     /   \                 /   
    A     B               cP    
   /       \             / \  
  /         \           /   \ 
 X           Z         A     B    
                      /     / 
                     cA    cB
                    /        \ 
                   X          Z
                  /          /     
                 cX        cZ      

2) Now given a node and it's clone (which is just node.left), the random pointer for the clone is: node.random.left (if node.random exists).

3) Finally, the binary tree can be un-interleaved.

I find this interleaving makes reasoning about the code much simpler.

Here is the code:

def clone_and_interleave(root):
    if not root:
        return

    clone_and_interleave(root.left)
    clone_and_interleave(root.right)

    cloned_root = Node(root.data)
    cloned_root.left, cloned_root.right = root.left, root.right

    root.left = cloned_root
    root.right = None # This isn't necessary, but doesn't hurt either.

def set_randoms(root):
    if not root:
        return

    cloned_root = root.left
    set_randoms(cloned_root.left)
    set_randoms(cloned_root.right)

    cloned_root.random = root.random.left if root.random else None

def unterleave(root):
    if not root:
        return (None, None)

    cloned_root = root.left
    cloned_root.left, root.left = unterleave(cloned_root.left)
    cloned_root.right, root.right = unterleave(cloned_root.right)

    return (cloned_root, root)


def cloneTree(root):
    clone_and_interleave(root)
    set_randoms(root)
    cloned_root, root = unterleave(root)

    return cloned_root