Traverse the tree, keep a hashtable with you and create a nodecopy for each node in the tree.
Start traversing the original tree again and connect the left, right and random pointers in the cloned tree the same way as the original tree with the help of the hashtable.