# Printing BFS (Binary Tree) in Level Order with _specific formatting_

### Question

To begin with, this question is not a dup of this one, but builds on it.

Taking the tree in that question as an example,

``````    1
/ \
2   3
/   / \
4   5   6
``````

How would you modify your program to print it so,

``````1
2 3
4 5 6
``````

rather than the general

``````1
2
3
4
5
6
``````

I'm basically looking for intuitions on the most efficient way to do it - I've got a method involving appending the result to a list, and then looping through it. A more efficient way might be to store the last element in each level as it is popped, and print out a new line afterward.

Ideas?

1
31
5/23/2017 12:18:02 PM

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;-).

64
12/12/2009 11:29:06 PM

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.