Vfrdtyky

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:

1

2 3

4 5 6

7

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

                    8

                   /  

                  1    12

                       /

                   5   9

                 /   

                4     7

                     /

                    6

o/p will be

  6

  7 4

  9 5

  12 1

  8

but the o/p has to be

  6

  4 7

  5 9

  1 12

  8

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

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

    1    

   /    

  2   3  

 /   /  

4   5   6

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.