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

Question

Hello,

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?

Answer 1

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.

Answer 2

compute from known arrayindex shall work. good sources are Baase & Allen Van Gelder, ford-fulkerson and alternative innovative datamodels heap, trie and red-black tree.

Answer 3

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

Answer 4

A version that doesn't require extra storage:

std::deque<Node> bfs;
bfs.push_back(start);
int nodesInThisLayer = 1;
int nodesInNextLayer = 0;
while (!bfs.empty()) {
    Node front = bfs.front();
    bfs.pop_front();
    for (/*iterate over front's children*/) {
        ++nodesInNextLayer;
        nodes.push_back(child);
    }
    std::cout << node.value;
    if (0 == --nodesInThisLayer) {
        std::cout << std::endl;
        nodesInThisLayer = nodesInNextLayer; 
        nodesInNextLayer = 0;
    } else {
        std::cout << " ";
    }
}

P.S. sorry for the C++ code, I'm not very fluent in Python yet.

Answer 5

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

public void printLevel(Node n) { Queue q = new ArrayBlockingQueue(); 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); } }