**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 data structure contains two pointers to other Nodes.**

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.

C++:

01 typedef map<Node*, Node*> NodeMap;

02 Node* copy_recursive(Node* cur, NodeMap& nodeMap){

03 if(cur==NULL){

04 return NULL;

05 }

06

07 NodeMap::iterator i=nodeMap.find(cur);

08 if(i!=nodeMap.end()){

09 //we have been here before, return the copy

10 return i->second;

11 }

12 Node* node=new node;

13 nodeMap[cur]=node; //map current before traversing links

14 node->ptr1=copy_recursive(cur->ptr1,nodeMap);

15 node->ptr2=copy_recursive(cur->ptr2,nodeMap)

16 return node;

17 }

18

19 Node* copy_structure(Node* root){

20 NodeMap nodeMap; //we will need an empty map

21 return copy_recursive(root, nodeMap);

22 }

02 Node* copy_recursive(Node* cur, NodeMap& nodeMap){

03 if(cur==NULL){

04 return NULL;

05 }

06

07 NodeMap::iterator i=nodeMap.find(cur);

08 if(i!=nodeMap.end()){

09 //we have been here before, return the copy

10 return i->second;

11 }

12 Node* node=new node;

13 nodeMap[cur]=node; //map current before traversing links

14 node->ptr1=copy_recursive(cur->ptr1,nodeMap);

15 node->ptr2=copy_recursive(cur->ptr2,nodeMap)

16 return node;

17 }

18

19 Node* copy_structure(Node* root){

20 NodeMap nodeMap; //we will need an empty map

21 return copy_recursive(root, nodeMap);

22 }

Advertisements