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

https://stackoverflow.com/questions/1894846

19-09-2019
|

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,

How would you modify your program to print it so,

1
2 3
4 5 6

rather than the general

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

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

OTHER TIPS

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

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

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:

A simple Version based on Bread First Search, This code is applicable for graphs in general and can be used for binary trees as well.

def printBfsLevels(graph,start):
  queue=[start]
  path=[]
  currLevel=1
  levelMembers=1
  height=[(0,start)]
  childCount=0
  print queue
  while queue:
    visNode=queue.pop(0)
    if visNode not in path:
      if  levelMembers==0:
        levelMembers=childCount
        childCount=0
        currLevel=currLevel+1
      queue=queue+graph.get(visNode,[])
      if levelMembers > 0:
        levelMembers=levelMembers-1
        for node in graph.get(visNode,[]):
          childCount=childCount+1
          height.append((currLevel,node))
      path=path+[visNode]

  prevLevel=None

  for v,k in sorted(height):
        if prevLevel!=v:
          if prevLevel!=None:
            print "\n"
        prevLevel=v
        print k,
  return height

g={1: [2, 3,6], 2: [4, 5], 3: [6, 7],4:[8,9,13]}
printBfsLevels(g,1)


>>> 
[1]
1 

2 3 6 

4 5 6 7 

8 9 13
>>>

Another version based on Recursion, which is specific to binary tree

class BinTree:
  "Node in a binary tree"
  def __init__(self,val,leftChild=None,rightChild=None,root=None):
    self.val=val
    self.leftChild=leftChild
    self.rightChild=rightChild
    self.root=root
    if not leftChild and not rightChild:
      self.isExternal=True

  def getChildren(self,node):
    children=[]
    if node.isExternal:
      return []
    if node.leftChild:
      children.append(node.leftChild)
    if node.rightChild:
      children.append(node.rightChild)
    return children

  @staticmethod
  def createTree(tupleList):
    "Creates a Binary tree Object from a given Tuple List"
    Nodes={}
    root=None
    for item in treeRep:
      if not root:
        root=BinTree(item[0])
        root.isExternal=False
        Nodes[item[0]]=root
        root.root=root
        root.leftChild=BinTree(item[1],root=root)
        Nodes[item[1]]=root.leftChild
        root.rightChild=BinTree(item[2],root=root)
        Nodes[item[2]]=root.rightChild
      else:
        CurrentParent=Nodes[item[0]]
        CurrentParent.isExternal=False
        CurrentParent.leftChild=BinTree(item[1],root=root)
        Nodes[item[1]]=CurrentParent.leftChild
        CurrentParent.rightChild=BinTree(item[2],root=root)
        Nodes[item[2]]=CurrentParent.rightChild
    root.nodeDict=Nodes
    return root

  def printBfsLevels(self,levels=None):
    if levels==None:
      levels=[self]
    nextLevel=[]
    for node in levels:
      print node.val,
    for node in levels:
      nextLevel.extend(node.getChildren(node))
    print '\n'
    if nextLevel:
      node.printBfsLevels(nextLevel)  


##       1
##     2     3
##   4   5  6  7
##  8

treeRep = [(1,2,3),(2,4,5),(3,6,7),(4,8,None)]
tree= BinTree.createTree(treeRep)
tree.printBfsLevels()

>>> 
1 

2 3 

4 5 6 7 

8 None

Here my code prints the tree level by level as well as upside down

int counter=0;// to count the toatl no. of elments in the tree

void tree::print_treeupsidedown_levelbylevel(int *array)
{
    int j=2;  
    int next=j;
    int temp=0;
    while(j<2*counter)
    {
        if(array[j]==0)
        break;

        while(array[j]!=-1)
        {
            j++;
        }

        for(int i=next,k=j-1 ;i<k; i++,k--)
        {
            temp=array[i];
            array[i]=array[k];
            array[k]=temp;
        }

        next=j+1;
        j++;
    }

    for(int i=2*counter-1;i>=0;i--)
    {
        if(array[i]>0)
        printf("%d ",array[i]);

        if(array[i]==-1)
        printf("\n");
    }
}

void tree::BFS()
{
    queue<node *>p;

    node *leaf=root;

    int array[2*counter];
    for(int i=0;i<2*counter;i++)
    array[i]=0;

    int count=0;

    node *newline=new node; //this node helps to print a tree level by level
    newline->val=0;
    newline->left=NULL;
    newline->right=NULL;
    newline->parent=NULL;

    p.push(leaf);
    p.push(newline);

    while(!p.empty())
    {
        leaf=p.front();
        if(leaf==newline)
        {
            printf("\n");
            p.pop();
            if(!p.empty())
            p.push(newline);
            array[count++]=-1;
        }
        else
        {
            cout<<leaf->val<<" ";
            array[count++]=leaf->val;

            if(leaf->left!=NULL)
            {
                p.push(leaf->left);
            }
            if(leaf->right!=NULL)
            {
                p.push(leaf->right);
            }
            p.pop();
        }
    }
    delete newline;

    print_treeupsidedown_levelbylevel(array);
}

Here in my code the function BFS prints the tree level by level, which also fills the data in an int array for printing the tree upside down. (note there is a bit of swapping is used while printing the tree upside down which helps to achieve our goal). If the swapping is not performed then for a tree like

o/p will be

but the o/p has to be

this the reason why swapping part was needed in that array.

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

class BST:
  def __init__(self, root):
    self._root = root

  def bfs(self):
    list = [self._root]
    while len(list) > 0:
        print [e.data for e in list]
        list = [e.left for e in list if e.left] + \
               [e.right for e in list if e.right]
bst = BST(TNode(1, TNode(2, TNode(4), TNode(5)), TNode(3, TNode(6), TNode(7))))
bst.bfs()

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)

The following code will print each level of binary tree into new line:

public void printbylevel(node root){
    int counter = 0, level = 0;
    Queue<node> qu = new LinkedList<node>();

    qu.add(root);
    level = 1;
    if(root.child1 != null)counter++;
    if(root.child2 != null)counter++;

     while(!qu.isEmpty()){
         node temp = qu.remove();
         level--;
         System.out.print(temp.val);
         if(level == 0 ){
             System.out.println();

             level = counter;
             counter = 0;
         }
        if(temp.child1 != null){
            qu.add(temp.child1);
            counter++;
        }
        if(temp.child2 != null){
            qu.add(temp.child2);
            counter++;
        }
     }
}

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.

For those who are simply interested in visualizing binary trees (and not so much in the theory behind breadth-first search), there is a show function in the binarytree package. Applied to the example given in the question,

from binarytree import Node, show

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.right.left = Node(5)
root.right.right = Node(6)

show(root)

which prints

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

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.

Licensed under: CC-BY-SA with attribution

Not affiliated with StackOverflow