StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Just build one level at a time, e.g.:</p> <pre><code>class Node(object): def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def traverse(rootnode): thislevel = [rootnode] while thislevel: nextlevel = list() for n in thislevel: print n.value, if n.left: nextlevel.append(n.left) if n.right: nextlevel.append(n.right) print thislevel = nextlevel t = Node(1, Node(2, Node(4, Node(7))), Node(3, Node(5), Node(6))) traverse(t) </code></pre> <p><strong>Edit</strong>: if you're keen to get a small saving in maximum consumed "auxiliary" memory (never having simultaneously all this level and the next level in such "auxiliary" memory), you can of course use <code>collection.deque</code> instead of <code>list</code>, and consume the current level as you go (via <code>popleft</code>) instead of simply looping. The idea of creating one level at a time (as you consume --or iterate on-- the previous one) remains intact -- when you do need to distinguish levels, it's just more direct than using a single big deque plus auxiliary information (such as depth, or number of nodes remaining in a given level).</p> <p>However, a list that is only appended to (and looped on, rather than "consumed") is quite a bit more efficient than a deque (and if you're after C++ solutions, quite similarly, a std::vector using just <code>push_back</code> for building it, and a loop for then using it, is more efficient than a std::deque). Since all the producing happens first, then all the iteration (or consuming), an interesting alternative <strong>if</strong> memory is tightly constrained might be to use a list anyway to represent each level, then <code>.reverse</code> it before you start consuming it (with <code>.pop</code> calls) -- I don't have large trees around to check by measurement, but I suspect that this approach would still be faster (and actually less memory-consuming) than <code>deque</code> (assuming that the underlying implementation of list [[or std::vector]] actually does recycle memory after a few calls to <code>pop</code> [[or <code>pop_back</code>]] -- and with the same assumption for deque, of course;-).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload