Take a pointer to a Node structure as a parameter and return a complete copy of the passed-in data structure

Problem

Write a method that takes a pointer to a Node structure as a parameter and returns a complete copy of the passed-in data structure. The Node structure contains two pointers to other Node structures.

Solution
The algorithm will maintain a mapping from a node address in the original structure to the corresponding node in the new structure. This mapping will allow us to discover previously copied nodes during a traditional depth first traversal of the structure. (Traversals often mark visited nodes--the mark can take many forms and does not necessarily need to be stored in the node.) Thus, we have a simple recursive algorithm:

struct Node {
    Node * ptr1;
    Node * ptr2;
};
 
typedef map<Node*, Node*> RecordMap;
 
Node * recursive_copy(Node * root, RecordMap & mapping) {
    if(root == NULL)
        return root;
    RecordMap::iterator i = mapping.find(root);
    if(i != mapping.end())
        // we’ve been here before, return the copy
        return mapping[root];
    else {
        Node * node = new Node;
        mapping[root] = node; // map current node
        node -> ptr1 = recursive_copy(root -> ptr1, mapping);
        node -> ptr2 = recursive_copy(root -> ptr2, mapping);
        return node;
    }
}
 
Node * copy_structure(Node * root) {
    RecordMap mapping; // we will need an empty map
    return recursive_copy(root, mapping);
}

References
http://tianrunhe.wordpress.com/2012/04/14/deep-copy-structure-of-pointers-in-c/
http://stackoverflow.com/questions/7681174/interview-coding-take-a-pointer-to-a-node-structure-as-a-parameter-and-return