Printing BFS (Binary Tree) in Level Order with Specific Formatting
My solution is similar to Alex Martelli's, but I separate traversal of the data structure from processing the data structure. I put the meat of the code into iterLayers to keep printByLayer short and sweet.
from collections import deque
class Node:
def __init__(self, val, lc=None, rc=None):
self.val = val
self.lc = lc
self.rc = rc
def iterLayers(self):
q = deque()
q.append(self)
def layerIterator(layerSize):
for i in xrange(layerSize):
n = q.popleft()
if n.lc: q.append(n.lc)
if n.rc: q.append(n.rc)
yield n.val
while (q):
yield layerIterator(len(q))
def printByLayer(self):
for layer in self.iterLayers():
print ' '.join([str(v) for v in layer])
root = Node(1, Node(2, Node(4, Node(7))), Node(3, Node(5), Node(6)))
root.printByLayer()
which prints the following when run:
1
2 3
4 5 6
7
Sounds like breadth-first traversal to me.
Breadth-first traversal is implemented with a queue. Here, simply insert in the queue a special token that indicate that a newline must be printed. Each time the token is found, print a newline and re-insert the token in the queue (at the end -- that's the definition of a queue).
Start the algorithm with a queue containing the root followed by the special newline token.
Just build one level at a time, e.g.:
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)
Edit: 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 collection.deque
instead of list
, and consume the current level as you go (via popleft
) 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).
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 push_back
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 if memory is tightly constrained might be to use a list anyway to represent each level, then .reverse
it before you start consuming it (with .pop
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 deque
(assuming that the underlying implementation of list [[or std::vector]] actually does recycle memory after a few calls to pop
[[or pop_back
]] -- and with the same assumption for deque, of course;-).