in place-ness of list.append

[skip at pobox.com]

    as> I'm pretty confident append itself (and a+[n]) are linear in
    as> N=len(a) ...

Yes, as I indicated in an earlier reply.  The overall construction of his
data structure would be O(N**2) or O(N*log N).  The latter is for binary
tree construction, but I didn't know what the OP was going to do with his
lists at the time I originally replied.

    as> Or, if you don't need to mutate the tree ``left = (parent,
    as> 1)``. Tuples ought to have a little less memory overhead.

Since at least 2.4, lists overallocate space for new entries proportional to
the current size of the list, so yes, tuples will be a bit friendlier,
certainly if your tree is very deep.

Skip