## Deep copy structure of pointers in C++

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.

My initial thoughts (code):

```struct Node {
Node * ptr1;
Node * ptr2;
};

Node * copy(Node * pass_in) {
Node * result = new Node();
result -> ptr1 = pass_in -> ptr1;
result -> ptr2 = pass_in -> ptr2;
}

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

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5c9102e892561', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5c9102e892587',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5c9102e892589',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});