One method that he didn't cover is storing fully-qualified paths. This gives
you efficient subtree querying and each node knows all of it's parents. I
haven't benchmarked this, but I think it will work well for low-depth trees.
I'll use ':' as the path separator so that it can be used unescaped in a
regex.
first insert documents like this and add an index on "path" (or just put it
in the _id field which is automatically indexed) :
{path: "a", data: STUFF}
{path: "a:b"}
{path: "a:c"}
{path: "a:c:d"}
{path: "e"}

You could then fetch the subtree rooted at "a" using find({path: /^a/}).
Mongo uses an index for all prefix queries so that will be very efficient.

If you are at node "a:c:d" and want the parent objects you can get that with
find({path: {$in: {'a', 'a:d'}}}).

I haven't benchmarked this against the other methods, but for subtree
searches this should be pretty good. Also, it should ensure a good locality
to your subtrees if you use the path as the shard-key.

If you have deep trees then either the parent_id or the child list method
would work well but will require many round trips (one per level) to fetch
whole sub-trees. Just make sure you index the children and parent_id fields.
You could always start by using all three methods and then see what works
best for you.

-Mathias