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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: