CareerCup

I propose the following: (i) Traverse the tree by a depth-firsr-search (DFS) and print the nodes as they come from a queue. (ii) The remaining thing is to detect the the new line (a change in the depth). This can be solved by queueing a null reference as shown in the code below:

public void printTree(Node root) {
    Queue<Node> q = LinkedList<Node>();
    q.add(root);
    q.add(null);     // null serves as a depth marker

    while (!q.isEmpty()) {
        Node curr = q.remove();
        if (curr != null) {
            System.out.print(curr.val+” ”);
            if (curr.left != null)      q.add(curr.left);
            if (curr.right != null)     q.add(curr.right);
        }
        else {
            System.out.println();     // print new line
            if (q.isEmpty())      break;
            q.add(null);
        }
    }
}

public class Node {
    public Node left;
    public Node right;
    public String val;
}

Use breadth first traversal will work with an addition that after traversal at each depth, you will have to return to the next line. This you can do by keeping an identifier, like null node.
Here is the code:

public class BstLevelOrderTraversal
    {
        public static void Traverse(BinaryTreeNode root)
        {
            if (root == null)
            {
                throw new ArgumentNullException("root");
            }

            Queue<BinaryTreeNode> q = new Queue<BinaryTreeNode>(2);
            q.Enqueue(root);
            
            while (q.Count != 0)
            {
                q.Enqueue(BinaryTreeNode.GetNullNode());
                while(!BinaryTreeNode.IsNullNode(q.Peek()))
                {
                    BinaryTreeNode temp = q.Dequeue();
                    System.Console.Write(temp.Value + " ");
                    if (temp.Left != null)
                        q.Enqueue(temp.Left);

                    if (temp.Right != null)
                        q.Enqueue(temp.Right);
                }

                System.Console.WriteLine();
                q.Dequeue();
            }

            q.Clear();
        }
    }

I will just give an algo to work around with (you can write a code in whichever language you want man):
Will use a queue Q (Working is same as BFS as Victor stated earlier)

1. Enqueue(Q, root)
2. Repeat steps 3-6 while Q is non empty
3. Dequeue(Q, node)
4. Process (node)
5. Enqueue(Q, leftChild(node))
6. Enqueue(Q, rightChild(node))
7. End

Just a simple BFS (python):

import sys

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

def tree_print(root):
    if not root:
        return
    queue = [root]
    while len(queue):
        children = []
        for node in queue:
            sys.stdout.write(node.val)
            for c in [node.left, node.right]:
                if c is not None:
                    children.append(c)
        sys.stdout.write('\n')
        queue = children

tree_print(
    Node('A', Node('B', Node('D'), Node('E')),
                     Node('C', Node('F'), Node('G', right=Node('Z')))
    )
)

package examples.algorithms;

import java.util.ArrayList;
import java.util.List;


public class PrintTreeTest {

public static void main(String[] args) {
Node tree= new Node('A');
Node left=new Node('B');
left.addLeft(new Node('D'));
left.addRight(new Node('E'));

Node right=new Node('C') ;
right.addLeft(new Node('F'));
right.addRight(new Node('G'));

tree.addLeft(left);
tree.addRight(right);
tree.print();
}


}
class Node {

private Node left;
private Node right;
private Character c;

public Node(Character c) {
this.c = c;
}
public void print(){
System.out.println(this.c);
print(this.left,this.right);
}
public void print(Node... nodes) {
List<Node> allSubNodes=new ArrayList<Node>();
for (Node node : nodes) {
if(node!=null){
System.out.print(node.c);
allSubNodes.add(node.left);
allSubNodes.add(node.right);
}
}

System.out.println("");
if(!allSubNodes.isEmpty()){
print(allSubNodes.toArray(new Node[allSubNodes.size()]));
}

}
public void addLeft(Node node){
this.left=node;
}
public void addRight(Node node){
this.right=node;
}

}

package examples.algorithms;

import java.util.ArrayList;
import java.util.List;


public class PrintTreeTest {

    public static void main(String[] args) {
        Node tree= new Node('A');
        Node left=new Node('B');
        left.addLeft(new Node('D'));
        left.addRight(new Node('E'));

        Node right=new Node('C') ;
        right.addLeft(new Node('F'));
        right.addRight(new Node('G'));

        tree.addLeft(left);
        tree.addRight(right);
        tree.print();
    }


}
class Node {

    private Node left;
    private Node right;
    private Character c;

    public Node(Character c) {
        this.c = c;
    }
    public void print(){
        System.out.println(this.c);
        print(this.left,this.right);
    }
    public void print(Node... nodes) {
        List<Node> allSubNodes=new ArrayList<Node>();
        for (Node node : nodes) {
            if(node!=null){
                System.out.print(node.c);
                allSubNodes.add(node.left);
                allSubNodes.add(node.right);
            }
        }

        System.out.println("");
        if(!allSubNodes.isEmpty()){
            print(allSubNodes.toArray(new Node[allSubNodes.size()]));
        }

    }
    public void addLeft(Node node){
        this.left=node;
    }
    public void addRight(Node node){
        this.right=node;
    }

}

def main():
  l = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
  bfs(l)

def bfs(t):
  queue = [[t[0], 0, 1]]
  visited = [0]
  prev_h = 1
  line = []
  while queue:
    el, i, h = queue.pop(0)
    l = 2*i + 1
    r = 2*i + 2
    if prev_h != h:
      print ''.join(line)
      prev_h = h
      line = [el]
    else:
      line.append(el)
    if len(t) > l and l not in visited:
      queue.append([t[l], i+1, (i-1)/2]) # n = 2*h- 1 => h = (n-1)/2
      visited.append(l)
    if len(t) > r and r not in visited:
      queue.append([t[r], i+1, (i-1)/2])
      visited.append(r)
  print ''.join(line)


if __name__ == '__main__':
  main()

ID (Iterative Deepening solution). Please recall that ID has same asymptotic time complexity as either BFS or DFS. The problem I have with all of the solutions above - it seems the problem is asking to separate each level one from another. I don't see anyone do that.

public static void printLevels(Node root) {
	int depth=0;
	while(printDepth(root, 0, depth) > 0){
		depth++;
		System.out.println();
	}
}
public static int printDepth(Node curNode, int curDepth, int targetDepth) {
	if (curDepth==targetDepth){
		System.out.print(curNode.val());
		return 1;
	}
	int sum=0;
	if (curNode.left() != null) {
		sum += printDepth(curNode.left(), curDepth+1,targetDepth);
	}
	if (curNode.right() != null) {
		sum += printDepth(curNode.right(), curDepth+1,targetDepth);
	}
	return sum;
}

BFS approach that is O(n) regarding the contents of the tree, and O(n) in memory consumption- more specifically, the maximal memory will never exceed half of n. Additionally, only 2 object constructions:

static class TreeNode{
	TreeNode left, right;
	char val;
}

public static void print(TreeNode node){
	LinkedList<TreeNode> list = new LinkedList<TreeNode>();
	LinkedList<TreeNode> alt = new LinkedList<TreeNode>();
	LinkedList<TreeNode> temp = null;
	list.add(node);
	while(!list.isEmpty()){
		print(list);
		while(!list.isEmpty()){
			node = list.removeFirst();
			if(node.left != null){
				alt.add(node.left);
			}
			if(node.right != null){
				alt.add(node.right);
			}
		}
		temp = list;
		list = alt;
		alt = temp;
	}
}

private static void print(LinkedList<TreeNode> list){
	Iterator<TreeNode> iter = list.iterator();
	StringBuilder b = new StringBuilder();
	while(iter.hasNext()){
		TreeNode node = iter.next();
		b.append(node.val);
	}
	java.lang.System.println(b.toString());
}

Assuming that it is binary tree

struct TreeNode{
  char content;
  TreeNode *left;
  TreeNode *right;
}

void printTree(TreeNode* root)
{
  Queue<TreeNode*> q, temp_q;
  
  q.enqueue(root);
  
  while(!q.IsEmpty()){ 
    while(!q.IsEmpty()){
      TreeNode *node = q.dequeue();
      
      if (node->left != null)
        temp_q.enqueue(node->left);
      if (node->right != null)
        temp_q.enqueue(node->right);
      
      cout<< node->content;
    }
    cout<<endl;
      
    while(!temp_q.IsEmpty())
      q.enqueue(temp_q.dequeue);
  }
}

This question is same as the one I was being asked few weeks ago.
careercup . com /question ? id=5169384622391296 (remove the space and paste onto your browser)

Break it down into two functions -- the first to breadth traverse the tree and store its values, and the other to print the stored values.

values[][];
int i = 0;

traverseTree (T, i) {
  push(values[i], T.value);
  traverseTree(T.leftChild, i+1) if T.leftChild;
  traverseTree(T.rightChild, i+1) if T.rightChild;
}

printTreeVals (values) {
  int i=0;
  while(values[i]) {
    foreach v in values[i] {
      print v;
    }
    print "\n";
  }
  i++;
}

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	static class Node
	{
		char value;
		Node left;
		Node right;
		
		public Node(char in)
		{
			this.value = in;
			this.left = null;
			this.right = null;
		}
	}
	static class Tree
	{
		Node root;
		
		public Tree(Node r)
		{
			this.root = r;
		}
		
		public  void treeBFS()
		{
			Queue<Node> queue = new LinkedList<Node>();
			
			queue.add(root);
			int count = 0;
			
			while(!queue.isEmpty())
			{
				if(count == 0)
				  count = queue.size();
				  
				Node c = queue.poll();
				count = count-1;
				if(c != null)
				{
					if(count == 0) 
					{
						System.out.print(" "+c.value);
						System.out.println(" ");
					}
					else
					{
						System.out.print(" "+c.value);
					}
					if(c.left != null);
					{
						queue.add(c.left);
					}
					if(c.right != null)
					{
						queue.add(c.right);
					}
				}
			}
		}
	}
	

	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Node A = new Node('A');
		Node B = new Node('B');
		Node C = new Node('C');
		Node D = new Node('D');
		Node E = new Node('E');
		Node F = new Node('F');
		Node G = new Node('G');
		
		A.left = B;
		A.right = C;
		
		B.left = D;
		B.right = E;
		
		C.left = F;
		C.right = G;
		
		Tree root = new Tree(A);
		root.treeBFS();
		
	}
}

At every level keep track of current level's nodes and next level's nodes as children. On enqueue, increment nextlevelnodes and on dequeue decrement currlevelnodes, when currlevelnodes becomes 0, print \n

void Tree::levelOrderHelper (TreeNode *root)
{
	if (root == NULL)
		return;
	TreeNode *node = NULL;
	queue<TreeNode *> listQ;
	listQ.push(root);
	cout<<endl;
	int numElemCurr = 1;
	int numElemNext = 0;
	while (!listQ.empty()) {
		node = listQ.front();
		cout<<(listQ.front())->data<<" ";
		listQ.pop ();
		numElemCurr--;
		if (node->leftPtr != NULL) {
			listQ.push (node->leftPtr);
			numElemNext++;
		}
		if (node->rightPtr != NULL) {
			listQ.push (node->rightPtr);
			numElemNext++;
		}
		if (numElemCurr == 0) {
			cout<<endl;
			numElemCurr = numElemNext;
			numElemNext = 0;
		}
	}
}

public class Tree {
	
	private String value;
	private Tree left;
	private Tree right;
	
	public Tree(String value, Tree left, Tree right){
		this.value = value;
		this.left = left;
		this.right= right;
	}

	public String getValue() {
		return value;
	}

	public void setValue(String value) {
		this.value = value;
	}

	public Tree getLeft() {
		return left;
	}

	public void setLeft(Tree left) {
		this.left = left;
	}

	public Tree getRight() {
		return right;
	}

	public void setRight(Tree right) {
		this.right = right;
	}
}

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

import com.mj.algo.tree.modal.Tree;

public class TreeTraversal {

	private Map<Integer, String> valuesMap = new HashMap<Integer, String>();
	
	private void printLevelOrder(Tree root, int level){
		//print values
		if(valuesMap.containsKey(level)){
			String value = valuesMap.get(level);
			value = value + root.getValue();
			valuesMap.put(level, value);
		}
		else{
			String value = root.getValue();
			valuesMap.put(level, value);
		}
		if(root.getLeft()!=null){
			printLevelOrder(root.getLeft(), level+1);
		}
		if(root.getRight()!=null){
			printLevelOrder(root.getRight(), level+1);
		}
	}
	

	private void printValueMap() {
	    Iterator it = valuesMap.entrySet().iterator();
	    while (it.hasNext()) {
	        Map.Entry pairs = (Map.Entry)it.next();
	        //System.out.println(pairs.getKey() + " = " + pairs.getValue());
	        System.out.println( pairs.getValue());
	        it.remove(); 
	    }
	}
	
	public static void main(String args[]){
		Tree child11 = new Tree("D", null, null);
		Tree child22 = new Tree("E", null, null);
		Tree child33 = new Tree("F", null, null);
		Tree child44 = new Tree("G", null, null);
		
		Tree child1 =  new Tree("B", child11, child22);
		Tree child2 =  new Tree("C", child33, child44);
		
		Tree root = new Tree("A", child1, child2);
		TreeTraversal treeTraversal = new TreeTraversal();
		treeTraversal.printLevelOrder(root,1);
		treeTraversal.printValueMap();
		
	}

}

This solution handles line breaks without adding extraneous null nodes to the queue.

#include <iostream>
#include <queue>

using namespace std;

struct Node
{
	Node *left;
	Node *right;
	char c;
};

void printTree(Node *root)
{
	queue<Node *> q;
	q.push(root);
	while (!q.empty())
	{
		int max = q.size();
		for (int i = 0; i < max; ++i)
		{
			Node *cur = q.front();
			cout << cur->c;
			if (cur->left) q.push(cur->left);
			if (cur->right) q.push(cur->right);
			q.pop();
		}
		cout << endl;
	}
}

I could not come up with a solution without using an intermediate list to keep the nodes.
Looking at other solutions, it seems it can be done without.

private void traverseInWidth(ArrayList<Node> list) {
        if (list.size() <= 0) {
            return;
        }

        ArrayList<Node> temp = new ArrayList<Node>();
        String data = "";
        for (int i = 0; i < list.size(); i++) {
            Node current = list.get(i);
            data += current.data;
            temp.addAll(current.children);
        }
        System.out.println(data);

        list.clear();
        traverseInWidth(temp);
    }

And it is called like this:

ArrayList<Node> list = new ArrayList<Node>();
        list.add(root);
        traverseInWidth(list);

Think I have a solution here, since there doesn't seem to be a way to do this without two temporary queues. Mine has O(n+h) time complexity, O(w+h) space complexity where h is the height of the tree and w is the maximum width of the tree.

Method:
1. Build a queue of the tree's right side
2. Do a level-order traversal of the tree using another queue
2a. For each object, print the character
2b. If the character matches the head of the queue, print a new line and pop from the queue.

Seems to do the job. Semi pseudo-code (hopefully no typos):

void printTree(BinaryTree *tree) {
  Queue rightSide = new Queue();
  Node *node = tree.root;
  while (root) {
    [rightSide push:root.object];
    root = root.rightChild;
  }
  
  Queue queue = new Queue();
  [queue addObject:tree.root];
  while (queue.count) {
    Node *node = queue.pop;
    
    printf("%s", node.object);
    if (node.object == rightSide.head) {
      printf("\n");
      [rightQueue pop];
    }
    
    if (node.leftChild) {
      [queue push:node.leftChild];
    }
    if (node.rightChild) {
      [queue push:node.rightChild];
    }
  }
}

public static void print(Tree node)
{

if ( node==NULL)
return;
Queue<Tree> Q= new LinkedList<Tree>();
Q.add(node);
while (!Q.empty())
{
node tmp=Q.remove();
if (tmp.left!=Q.element())
System.out.println(tmp.data+"\n");
else
System.out.println(tmp.data);
if (tmp.left !=NULL)
Q.add(tmp.left);
if ( tmp.right!=NULL)
Q.add(tmp.right);
}
}

public static void print(Tree node)
{

if ( node==NULL)
return;
Queue<Tree> Q= new LinkedList<Tree>();
Q.add(node);
while (!Q.empty())
{
node tmp=Q.remove();
if (tmp.left!=Q.element())
System.out.println(tmp.data+"\n");
else
System.out.println(tmp.data);
if (tmp.left !=NULL)
Q.add(tmp.left);
if ( tmp.right!=NULL)
Q.add(tmp.right);
}
}

Level order travesal

string function BinaryTreeToString(Node *node)
{
    Queue q = new Queue();
    q.enqueue(node);
    string strTree = "";
    int counter = 1;
    int powCounter = 1;
    
    while(q.size)
    {
        Node *node = q.dequeue();
        if(node->left() != null)
        {
            q.enqueue(node->left());
        }    
        if(node->right() != null))
        {
            q.enqueue(node->right());
        }
        
        strTree += node.value;     
        if(counter == powCounter) //Since its a binary tree, we want to put \n after every tree level   
        {                         //And we know how many elements we got on each level(2^0\n2^1\n...2^n)
            strTree += "\n";
            powCounter = pow(2, counter);
            counter = 0; 
        }
        else
        {
            counter++;
        }
    }
    
    return strTree;
}

void PrintLevelOrder(Node* root)
{
	if (root == NULL)
	{
		return;
	}

	Node* currNode = NULL;
	queue<Node*> tempQueue;
	tempQueue.push(root);
	int currlevelcount = 1, nextlevelcount = 0;
	while (!tempQueue.empty())
	{
		currNode = tempQueue.front();
		tempQueue.pop();
		currlevelcount--;
		if (currNode != NULL)
		{
			cout << currNode->data;
			tempQueue.push(currNode->left);
			tempQueue.push(currNode->right);
			nextlevelcount += 2;
		}
		if (currlevelcount == 0)
		{
			cout << endl;
			currlevelcount = nextlevelcount;
			nextlevelcount = 0;
		}
		
	}
}

public static void main(BTNode root){
System.out.print(root.data + " ");
bfsTraversalMy(root);
}

public static void bfsTraversalMy(BTNode node) {

if(node == null){
return;
}

if(node.left != null){
System.out.print(node.left.data +" ");
}

if(node.right != null){
System.out.print(node.right.data + " ");
}


bfsTraversalMy(node.left);
bfsTraversalMy(node.right);
}

package Graphs;

import java.util.LinkedList;
import java.util.Queue;

public class LevelOrderTraversal {

	public static void printLevelOrder(Node root) {

		if(root == null) return;
		
		Queue<Node> q = new LinkedList<Node>();
		q.add(root);
		q.add(null); // add marker here

		while (!q.isEmpty()) {
			Node c = q.remove();

			if (c == null) {
				System.out.println();
				if(!q.isEmpty()) q.add(null); // must check empty else will get in to infinite recurssion
			} 
			else {
				
				System.out.print(c.data);
				
				// insert left and right child
				if (c.left != null)
					q.add(c.left);
				if (c.right != null)
					q.add(c.right);
			
			}
		}
		
		
		
		
		
		
		
		
		
		
	}

}

public class LevelOrderTraversal {

	public static void printLevelOrder(Node root) {

		if(root == null) return;
		
		Queue<Node> q = new LinkedList<Node>();
		q.add(root);
		q.add(null); // add marker here

		while (!q.isEmpty()) {
			Node c = q.remove();

			if (c == null) {
				System.out.println();
				if(!q.isEmpty()) q.add(null); // must check empty else will get in to infinite recurssion
			} 
			else {
				
				System.out.print(c.data);
				
				// insert left and right child
				if (c.left != null)
					q.add(c.left);
				if (c.right != null)
					q.add(c.right);
			
			}
		}
		
		
		
		
		
		
		
		
		
		
	}

}

void levelOrder(TreeNode root) {
	LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
	
	queue.addLast(root);
	queue.addLast(null);
	while (!queue.isEmpty()) {
		TreeNode p = null;
		while ((p = queue.removeFirst()) != null) {			
			System.out.print(p.val + " ");
			if (p.left != null) {
				queue.addLast(p.left);
			}
			if (p.right != null) {
				queue.addLast(p.right);
			}
		}
		
		if (!queue.isEmpty()) {
			queue.addLast(null);
			System.out.println("");
		}
	}
}

C++ version of solution using BFS.

#include <list>
#include <iostream>
using namespace std;

struct node {
	node* left;
	node* right;
	int value;
	node(int v):value(v),left(0), right(0){}
};

void print_tree(node * root)
{
	list<node *>queue;
	int cur_children = 0;
	int next_children = 0;

	if (!root)
		return;

	queue.push_back(root);
	cur_children++;
	while(queue.size())
	{
		node* cur = queue.front();
		queue.pop_front();
		if (cur->left)
		{
			queue.push_back(cur->left);
			next_children++;
		}
		if (cur->right)
		{
			queue.push_back(cur->right);
			next_children++;
		}
		cout<<cur->value<<" ";
		if (--cur_children == 0)
		{
			cout<<endl;
			cur_children = next_children;
			next_children = 0;		
		}
	}
}

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	static class Node
	{
		char value;
		Node left;
		Node right;
		
		public Node(char in)
		{
			this.value = in;
			this.left = null;
			this.right = null;
		}
	}
	static class Tree
	{
		Node root;
		
		public Tree(Node r)
		{
			this.root = r;
		}
		
		public  void treeBFS()
		{
			Queue<Node> queue = new LinkedList<Node>();
			
			queue.add(root);
			
			while(!queue.isEmpty())
			{
				Node c = queue.poll();
				if(c != null)
				{
					System.out.print(" "+c.value);
					if(c.left != null);
					queue.add(c.left);
					if(c.right != null)
					queue.add(c.right);
				}
			}
		}
	}
	

	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Node A = new Node('A');
		Node B = new Node('B');
		Node C = new Node('C');
		Node D = new Node('D');
		Node E = new Node('E');
		Node F = new Node('F');
		Node G = new Node('G');
		
		A.left = B;
		A.right = C;
		
		B.left = D;
		B.right = E;
		
		C.left = F;
		C.right = G;
		
		Tree root = new Tree(A);
		root.treeBFS();
		
	}
}

It would be great, if the question poster also state, in what manner the tree was represented as an input parameter for this reqd function to be written?