Saturday, April 5, 2014

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


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



Post a Comment