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

Question

This is an interview question that I found interesting.

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. For example, the method signature could look like so:

Node* Copy(Node* root);

---

Note - Do not make any assumptions about the data structure – it could be a tree, linked list, graph, etc.

How can this be done for any data structure ?

Answer 1

In the generic graph case, you need a mapping from nodes in the original graph to nodes in the new graph, so that when a cycle is encountered, the proper link gets created. If you happen to have extra temporary space in each node, large enough to hold a pointer, then you can store the mapping directly in the nodes; otherwise, you'll need to use an external map, such as an associative array or hash table.

Then it's just a matter of traversing the graph, copying nodes, and looking up the corresponding edges. Something like this:

struct Node
{
    Node(int _data) : data(_data) { memset(links, 0, sizeof(links)); }

    int data;
    Node *links[2];
}

Node *Copy(Node *root)
{
    typedef std::map<Node*, Node*> NodeMap;
    NodeMap nodeMap;
    std::deque<Node*> nodesToVisit;

    // Set up initial new root and mapping for the root
    Node *newRoot = new Node(root->data);
    nodeMap[root] = newRoot;

    // Breadth-first search the graph
    nodesToVisit.push_back(root);

    while(!nodesToVisit.empty())
    {
        Node *cur = nodesToVisit.front();
        nodesToVisit.pop_front();

        Node *newCur = nodeMap[cur];
        for(int i = 0; i < 2; i++)
        {
            Node *link = cur->links[i];
            if(link)
            {
                // If we've already created the corresponding node for this
                // link, use that.  Otherwise, create it and add it to the map.
                NodeMap::iterator mappedLink = nodeMap.find(link);
                if(mappedLink != nodeMap.end())
                {
                    newCur->links[i] = mappedLink->second;
                }
                else
                {
                    Node *newLink = new Node(link->data);
                    nodeMap[link] = newLink;
                    newCur->links[i] = newLink;
                    nodesToVisit.push_back(link);
                }
            }
        }
    }

    return newRoot;
}

Answer 2

The problem as stated is impossible. You have to assume that the entire data structure is stored entirely within the content of nodes that are accessible from that initial one. But that is not an assumption you are allowed to make. Even your standard basic double linked list might not fit that description.

Answer 3

class Copier {
  std::map <Node*, Node*> copies;

  Node* Copy(Node* n) {
    if (!n) return 0;
    Node*& copy = copies[n];
    if (!copy) {
      copy = new Node();
      copy.node1 = Copy(n.node1);
      copy.node2 = Copy(n.node2);
    }
    return copy;
  }
}