<blockquote> The general fix is to add an additional integer column
called (say) "max_leaf" to each node , which can be
used directly, avoiding the need to traverse all the
children of a node when adding a new child.
</blockquote>
But wouldn't it require additional time to update it (albeit this may still be better than current state)?
Maybe Oracle-like CONNECT BY for Pg should be given a try?
