Printing BFS (Binary Tree) in Level Order with Specific Formatting

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

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.

This is mostly the same code as provided by Alex Martelli except this is modified for python 3.

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,' ', end=''),
      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)

I think what you expecting is to print the nodes at each level either separated by a space or a comma and the levels be separated by a new line. This is how I would code up the algorithm. We know that when we do a breadth-first search on a graph or tree and insert the nodes in a queue, all nodes in the queue coming out will be either at the same level as the one previous or a new level which is parent level + 1 and nothing else.

So when you are at a level keep printing out the node values and as soon as you find that the level of the node increases by 1, then you insert a new line before starting to print all the nodes at that level.

This is my code which does not use much memory and only the queue is needed for everything.

Assuming the tree starts from the root.

queue = [(root, 0)]  # Store the node along with its level. 
prev = 0
while queue:
  node, level = queue.pop(0)
  if level == prev:
    print(node.val, end = "")
  else:
    print()
    print(node.val, end = "")
  if node.left:
    queue.append((node.left, level + 1))
  if node.right:
    queue.append((node.right, level + 1))
  prev = level

At the end all you need is the queue for all the processing.

Here is a Python gist which prints the tree by level. The idea behind it is to use BFS and keep a level marker integer which marks the end the last node of the level. This is similar to Naresh's sentinel approach, but without the need of inserting a sentinel inside the queue, since this is accomplished by the level marker.

This algorithm has a space complexity of O(2^tree_height)

# Print tree by levels - using BFS
# Time complexity of O(n)
# Space complexity: O(2^tree_height)

from collections import deque

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def print_levels_tree(root: Node):
    q = deque()
    q.append(root)
    level, level_marker = 0, 1
    while q:
        if (level_marker == 0):
            level, level_marker = level + 1, len(q)
            print("", end = '\n')
        level_marker -= 1

        node = q.popleft()

        if (node is None):
            continue

        print(node.data, " ", end = '')

        q.append(node.left)
        q.append(node.right)


# Some examples
tree = Node(19, Node(7, Node(3), Node(11)), Node(19)) 
print_levels_tree(tree)

left = Node(7, Node(3, Node(2), Node(5)), Node(11, None, Node(17, Node(13))))
tree = Node(19, left, Node(43))
print_levels_tree(tree)

left = Node(7, Node(3, Node(2), Node(5)), Node(11, None, Node(17, Node(13))))
right = Node(43, Node(23, None, Node(37, Node(29, None, Node(31)), Node(41))), Node(47, None, Node(53)) )
tree = Node(19, left, right)
print_levels_tree(tree)

Which prints something like:

19  
7  43  
3  11  23  47  
2  5  17  37  53  

If you want to use a \t separator, it would look like:

19  
7   43  
3   11  23  47  
2   5   17  37  53  

This gist is available at https://gist.github.com/lopespm/993f0af88cf30b7f8c9e17982518b71b

Making use of queues(constant space complexity)

def bfs(self, queue=None):
    
    if(queue is None):
        queue = deque([self.root])
        
    elif(not queue):
        return

    currNode  = queue.pop()
    
    print(currNode.data)
    
    if currNode.left:
        queue.appendleft(currNode.left)
        
    if currNode.right:
        queue.appendleft(currNode.right)
    
    self.bfs(queue)

LEVEL ORDER TRAVERSAL of a BT / BST

In BASH, you can easily implement BT / BST without using any hash arrays/map, etc by simply creating/maintaining nodes in a .txt file.

Here's my crack at it. 2 small functions print_level() and print_root(), will do. Script can print any level node info from any given user specified root node.

#!/bin/bash

print_level(){
 echo $cs

 call_flag=0
 for row in $cs; do if [[ `grep "^${row}:" ~/btree-data.txt` ]]; then call_flag=1; fi; done

 if [[ $call_flag == 1 ]]; then rs="$cs"; print_root; fi
}

print_root(){
  if [[ ${flag} == 0 ]]; then echo "${rs}"; flag=1; fi

  cs=""
  for r in $rs; do cs+="$(grep "^${r}:" ~/btree-data.txt | cut -d':' -f2 | sed "s/,/ /") "; done
  print_level
  echo
}

flag=0
echo -e "\n\n
# It reads a file ~/btree-data.txt (as shown below). 
# -- One can easily implement CRUD operation to maintain BT/BST using a .txt file. 
#
# -- Here .txt file ROW's Format is: NODE:left_leaf_node,right_leaf_node
#
# 100:50,200
# 50:20,60
# 200:300
# 300:350
# 60:55,75
# 20:10,25
# 10:5
# 350:320
# 25:27
# 5:2
# 320:310,325
# 2:3

## ----------------- BTree Diagram -------------------------------------------------------------------------
#                                                             100
#                                             50                               200
#                              20                       60                             300
#                        10          25             55       75                                      350
#                    5                     27                                                  320
#              2                                                                           310     325
#                 3
## ----------------- BTree Diagram -------------------------------------------------------------------------
\n\n"

echo -ne "\n-- Enter which root: "; read rs

print_root
echo -e "\n\n"

Which when you run, spits:

$ ./btree-bash-level-print.sh

# It reads a file ~/btree-data.txt (as shown below). 
# -- One can easily implement CRUD operation to maintain BT/BST using a .txt file. 
#
# -- Here .txt file ROW's Format is: NODE:left_leaf_node,right_leaf_node
#
# 100:50,200
# 50:20,60
# 200:300
# 300:350
# 60:55,75
# 20:10,25
# 10:5
# 350:320
# 25:27
# 5:2
# 320:310,325
# 2:3

## ----------------- BTree Diagram -------------------------------------------------------------------------
#                                                             100
#                                             50                               200
#                              20                       60                             300
#                        10          25             55       75                                      350
#                    5                     27                                                  320
#              2                                                                           310     325
#                 3
## ----------------- BTree Diagram -------------------------------------------------------------------------




-- Enter which root: 100
100
50 200
20 60 300
10 25 55 75 350
5 27 320
2 310 325
3

For root (300),

-- Enter which root: 300
300
350
320
310 325

For root (50),

-- Enter which root: 50
50
20 60
10 25 55 75
5 27
2
3

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.