It should never happen if you're responding to the on_tree_edge. The nice thing is that the discovery of edges in a BFS (and DFS and the MST algorithms) is that id builds a tree, meaning that every node has only one parent.

If you do have multiple parents (aka polytree)... I'm not sure. You could invert the process and have each child start waiting on a semaphore initialized with its number of parents (I forget the exact terminology). Each parent signals the semaphore when its done, and the child thread will be woken up when the semaphore reaches 0. I think you can do this with condition variables also.