If objects can only be added, but not removed, then things are a bit simpler. You can allocate the new object from a thread-safe pool, initialize the new object, and then atomically set a pointer to it in the parent object.
@Hodgman I'm trying to make sure that the objects in my scene graph can be accessed from other threads and have objects added to them. But I want to use locks as little as possible. Although, I guess adding child objects might be something that doesn't happen very often.
...however, now if someone is iterating the graph at the same time that someone is adding nodes, it's random as to whether the new nodes will be iterated or not. So I'd still recommend you break your program into different passes/stages, e.g. a read stage and a modify stage.