representing a tree as a list in python
<p>I'm learning python and I'm curious about how people choose to store (binary) trees in python. </p>

<p>Is there something wrong in storing the nodes of the tree as a list in python? something like:</p>

<pre><code>[0,1,2,3,4,5,6,7,8]
</code></pre>

<p>where the 0'th position is 0 by default, 1 is the root, and for each position (i), the 2i and 2i+1 positions are the children. When no child is present, we just have a 'None' in that position. </p>

<p>I've read a couple of books/notes where they represent a tree using a list of lists, or something more complicated than just a simple list like this, and I was wondering if there's something inherently wrong in how i'm looking at it?</p>

<p>I've seen representations like this (your flat list/array) used in C code, and representations like this could be acceptable in Python too, but it depends on the nature of the data you're handling. In C code, a balanced tree in this list representation can be very fast to access (much quicker than navigating a series of pointers), though the performance benefit in Python may be less noticeable due to all the other overhead.</p>

<p>For reasonably balanced dense trees, this flat list approach is reasonable. However, as Adam Smith commented, this type of flat list tree would become extremely wasteful for unbalanced sparse trees. Suppose you have one branch with single children going down a hundred levels, and the rest of the tree had nothing. You would need 2^100 + 2^99 + 2^98 + ... + 2^1 + 1 spots in the flat list tree. For such a case, you would use up a huge amount of memory for something that could be represented much more efficiently with nested lists.</p>

<p>So in essence, the choice between flat list trees vs. nested list trees is similar to the choice between flat array trees and pointer based trees in a C like language.</p>

python binary-tree