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?

Solution 1

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

Solution 2

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.

Solution 3

This is breadth first search, so you can use a queue and recursively do this in a simple and compact way ...

# built-in data structure we can use as a queue
from collections import deque

def print_level_order(head, queue = deque()):
    if head is None:
        return
    print head.data
    [queue.append(node) for node in [head.left, head.right] if node]
    if queue:
        print_level_order(queue.popleft(), queue)

Solution 4

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

Solution 5

why not keep sentinal in queue and check when all the nodes in current level are processed.

public void printLevel(Node n) {
    Queue<Integer> q = new ArrayBlockingQueue<Integer>();
    Node sentinal = new Node(-1);
    q.put(n);
    q.put(sentinal);
    while(q.size() > 0) {
        n = q.poll();
        System.out.println(n.value + " "); 
        if (n == sentinal && q.size() > 0) {
           q.put(sentinal); //push at the end again for next level
           System.out.println();
        }
        if (q.left != null) q.put(n.left);
        if (q.right != null) q.put(n.right);
    }
}

View more solutions

Comments

[viksit]

Yes, I mentioned the BFS part in the title :) I was thinking about the newline in the queue as well, but it seems wrong to intersperse formatting tokens within the queue itself.

[Andreas Brinck]

@Viksit Would it be more acceptible to store the depth of each node in the queue? In that case you could simply print a newline each time the current traversal depth is increased.

[Pascal Cuoq]

Ah, yes, "BFS"... I see what this three-letter acronym means now. Is the "S" for search? Isn't "search" always depth-first (or you built your binary tree wrong in the first place)?

[Pascal Cuoq]

@Andreas Nice! I was a little reluctant to mix special tokens and nodes in the queue too (but you have to do what you have to do...)

[Andreas Brinck]

@Pascal I actually thought a little more and came up with a version that didn't require any extra storage whatsoever :)

[viksit]

@Pascal - ah, I guess I've always referred to depth first and breadth first traversals as DFS and BFS respectively..

[viksit]

@Andreas - nice! I was looking at a version of this algorithm where I would store the "level" or "depth" of where the loop was (so, this tree would have 3 levels). The problem I faced was how to increment this level each time. Looks like your approach of storing the depth of each element works better.

[Andreas Brinck]

@Viksit If you look closer I only stores two extra integers, one for how many nodes are left to process in the current level and one for how many nodes are left to process in the next level (Or was this what you meant?)

[Andreas Brinck]

+1 I can see how using two vectors for the two levels could be more efficient than using a single deque. Especially if nextLevel is moved outside the while-loop and cleared instead of allocating a new one on the stack for each level (this is the C++ version I'm talking about, I've no idea how memory is managed in Python). This would also allow for very good cache utilization.

[Alex Martelli]

Yes, in C++ you'd definitely want to swap the vectors (and clear out the new one -- with the old one's contents -- right after that, if you're looping on it rather than using pop_back). In Python you could do thislevel[:] = nextlevel, then if needed del nextlevel[:], with similar effect (though I'm not sure the actual performance improvement would be measurable, it sure can't hurt;-).

[viksit]

@Alex - thanks for a great answer. The note on the iteration vs consumption of lists was quite informative!

[Sam]

This answer isn't in Python

[user1767754]

That's not python

[Geoff Langenderfer]

from binarytree import build; root = build([3,1,2]); print(root) Thank you sir

[Geoff Langenderfer]

build2 was a more intuitive transformation from list to tree for me

[CharlesB]

This does BFS traversal but without level distinction (no newline at the end of each level)