I'm dealing with this exact problem right now. I'm looking at MongoDB, CouchDB, and Postgres.
I agree that Postgres can do this - I've done it before. But I think you're a bit wrong to dismiss document databases so quickly.
Firstly, the subtree update problem isn't a huge problem. MongoDB allows dot notation to update items within a document. Yes, it is may well have to do just as much work as a SQL database in the update case, but I don't care. I'd prefer it is implemented in the database than something I have to do myself.
Secondly, the schema-free nature of a document database is a killer-feature for me. I have truly schema-free tree data (different levels of the tree have different, unknowable-in-advance data stored against them). Yes, I can implement this in a SQL database schema, but it's going to be an ugly schema (eg, I'll have to use rows to store things that should be columns). It will also be slow because of the hierarchical walking needed in the queries. (Although Postgres helps some here with hierarchical query support).
To your "first", I continue to state: that could be handled in a library. There is no reason why this is better handled inside rather than outside of the database. Insisting that this be provided by the database vendor instead of as a layer on top, however, means that you are now taking an entire backend storage implementation (one that is incredibly touchy, I will mind you: I've been using MongoDB in production for the last eight months and I now consider myself an idiot for having wasted time with it) from someone because they provided a convenient syntax.
To your "second": that is not a property of your usage of trees, and starts a new, unrelated discussion. I have nothing against document-oriented databases, and use them often. I feel you are blurring the line between syntax and implementation with your "slow" comment (again: if you are able to concurrently update those schema-less data items you are going to be taking the same hit you would be getting with any other backend for the separate storage and indexing), but will certainly not argue that there are classes of problems where document-oriented databases are really useful. However, trees in particular are not one of their killer features.
I agree that Postgres can do this - I've done it before. But I think you're a bit wrong to dismiss document databases so quickly.
Firstly, the subtree update problem isn't a huge problem. MongoDB allows dot notation to update items within a document. Yes, it is may well have to do just as much work as a SQL database in the update case, but I don't care. I'd prefer it is implemented in the database than something I have to do myself.
Secondly, the schema-free nature of a document database is a killer-feature for me. I have truly schema-free tree data (different levels of the tree have different, unknowable-in-advance data stored against them). Yes, I can implement this in a SQL database schema, but it's going to be an ugly schema (eg, I'll have to use rows to store things that should be columns). It will also be slow because of the hierarchical walking needed in the queries. (Although Postgres helps some here with hierarchical query support).