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

Problem

See also