Memory overhead for trees?

[Paul Rubin]

pinard at iro.umontreal.ca (François Pinard) writes:
> I'm toying with the idea of converting an existing LISP system into Python.
> The system uses a lot of real trees, I mean, more deep than wide on average.
> Trees are traversed and explored a great deal, but modified relatively less
> often.  I'm seeking a representation which, while being reasonably efficient
> -- yet no miracles are expected here! -- is not too voracious on memory.

If it's a binary tree that's reasonably balanced, the usual
representation is a linear array like in the heapsort algorithm. 
a[0] is the root; and for any node a[i], the node's children are
a[2*i+1] and a[2*i+2].