@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.

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.
...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.

Well if I break it up into different stages then wouldn't that be basically the same as having a serial program? Or do you mean something like: a node has a list of children, but when you call addChild it would instead add the child to another list that gets merged with the main "update" list in the beginning of the node's update function? And then I could do the same thing for removals too right? So any modifications to the list would be queued up and deferred until the beginning of the object's update, before any iterating was done in the frame. Or by breaking it into stages do you mean I need to radically alter the entire architecture of my engine?

Well if I break it up into different stages then wouldn't that be basically the same as having a serial program? Or do you mean something like: a node has a list of children, but when you call addChild it would instead add the child to another list that gets merged with the main "update" list in the beginning of the node's update function? And then I could do the same thing for removals too right? So any modifications to the list would be queued up and deferred until the beginning of the object's update, before any iterating was done in the frame. Or by breaking it into stages do you mean I need to radically alter the entire architecture of my engine?

Sorry I missed this reply.
Yes, queueing up modifications instead of performing them immediately is a good way to break up processing into several stages and reduce the amount of communication between threads.

Also, breaking algorithms into serial stages isn't the same as a serial program -- often many threads can contribute to each stage, and different threads can be working on different problems at the same time.
e.g. say we've got a single-threaded function, C, and two functions A & B that can be completed by parallel worker threads. Let's also say that A & B can also be split into 2 stages, and the code we're trying to execute looks like:
result = C( A(), B() )
Given 3 worker threads, their progress over time (vertical) could look like:
#0 #1 #2
A1 A1 B1
B1 B1 A1
A2 A2 B2
B2 B2 A2
C .wait.

I once read a wise statement on a forum saying that a container generally cannot make itself threadsafe on behalf of its client.

The thread safety generally needs to be done by the code using the container, because it inevitably needs to lock the container whilst performing more than one action with it. Thus this is a flawed endevaour, a "fool's errand" so to speak.