There are a few ways to phrase the same question.
- For a connected graph of colored nodes (say, only a few colors or black/white), you are given one node only. Please clone entire graph.
- Given one node in a connected graph, visit every node and recreate entire graph in another computer.
- Given one node in a directed graph, serialized it, transmit to another computer and deserialize.
I feel this is one of the most practical algo problems. I feel my solution is fairly efficient for binary tree too.
Not too hard conceptually, if your mental picture is clear. I would need to assign node IDs (based on addresses ) to differentiate the black nodes. These IDs are serialized. So are the edge lists .
— For serialization, Basic idea is a BFT (or DFT) to visit every node. Each time a node address is encountered again (probably among the edge list of some node), we would simply skip it.
Within each node, the this->edges field is “translated” and serialized as a list or treeSet of node_IDs. The serialized file looks like
- ID=1, edges=3,4,5,6
- ID=2, edges=3,5,7
- ID=3, edges=5,7,9
- ID=4, edges=6,8
I think serialization is O(V+E). I think same O() for deserialization.
— For deserialization, we can simply construct all node objects in an array, using ID as index. The edge list can stay as is. Optionally, we translate each edge from an ID into an address in the array.
 these are basic algoQQ pointers