CareerCup

Use 2 Queues. When printing nodes from Q1 enqueue their children in Q2 and VICE-VERSA. When Q1 or Q2 becomes empty while printing the node then print a new line.

Below is a simple implementation of the level order scan application using a single queue along with the driver program.
Also pasting the output.

#include <stdio.h>
#include <queue>

struct Node {
    Node* left;
    Node* right;
    int data;
};

static Node g_Nodes[] = { 
           {NULL, NULL, 17},
           {NULL, NULL, 5},
           {NULL, NULL, 9},
           {NULL, NULL, 12},
           {NULL, NULL, 28},
           {NULL, NULL, 1 },
           {NULL, NULL, 20},
           {NULL, NULL, 40},
           {NULL, NULL, 38},
           {NULL, NULL, 8 },
};

void bst_add(Node *pRoot, Node *pNew)
{
    if (pNew->data < pRoot->data) {
        if (NULL == pRoot->left)
            pRoot->left = pNew;
        else
            bst_add(pRoot->left, pNew);
    }
    else {
        if (NULL == pRoot->right)
            pRoot->right = pNew;
        else
            bst_add(pRoot->right, pNew);
    }
}

Node* bst_init()
{
    Node *pRoot = &g_Nodes[0];
    int cnt, i;
    
    cnt = sizeof(g_Nodes)/sizeof(g_Nodes[0]);
    
    for (i = 1; i < cnt; i++){
        Node *pTmp = &g_Nodes[i];
        bst_add(pRoot, pTmp);
    }
    
    return pRoot;
}

void bfs_scan_tree(Node *pNode)
{
    int cur, nxt;
    
    if (NULL == pNode)
        return;
        
    std::queue<Node*> Q;
    
    Q.push(pNode);
    cur = 1;
    nxt = 0;
    
    while (! Q.empty()) {
        Node *ptmp = Q.front();
        Q.pop();
        
        /* Add the children of this node to the queue */
        if (ptmp->left){
            Q.push(ptmp->left);
            nxt++;
        }
        if (ptmp->right){
            Q.push(ptmp->right);
            nxt++;
        }
        
        /* Process the current node and decrement the current counter */
        printf("%-2d ", ptmp->data);
        cur--;
        
        /* Check if we have completed printing all the 
           nodes of the current level and process that case.
        */
        if (0 == cur) {
            cur = nxt;
            nxt = 0;
            printf("\n");
        }
    }
}

int main(int argc, char *argv[])
{
    Node *pRoot = bst_init();
    bfs_scan_tree(pRoot);
    return 0;
}

17
5 28
1 9 20 40
8 12 38

We can use BFS to implement this. In BFS nodes at a level are processed before heading on to the next level nodes.

// Using only one queue and without any marker.

void print(node *root){
    queue<node *> q;
    
    q.push(root);
    int parent_nodes = 1;
    int child_nodes = 0;
    while(!q.empty()){
        node *t = q.front();
        q.pop();
        
        parent_nodes -= 1;
        cout<<t->val<<" ";
        if(t->left) {
            q.push(t->left);
            child_nodes += 1;
        }
        if(t->right) {
            q.push(t->right);
            child_nodes += 1;
        }
        
        if(parent_nodes == 0){
            cout<<"\n";
            parent_nodes = child_nodes;
            child_nodes = 0;
        }
    }
}

using 2 queues...is run time linear???

Using the following code we can print the levels
with using only one queue.

void levelorder(struct node * root)
{
struct node * temp = root;
int quesize = 0;
if(root==NULL)
return;
cout<<temp->data<<",";
while(temp!=NULL)
{
if(temp->left!=NULL)
mynodequeue.push(temp->left);
if(temp->right!=NULL)
mynodequeue.push(temp->right);
if(quesize ==0)
{
quesize = mynodequeue.size();
cout<<endl;
//temp1 = NULL;
}

temp = mynodequeue.front();
mynodequeue.pop();
quesize--;

cout<<temp->data<<",";
//cout<<temp1->data<<"(next),";

if(mynodequeue.empty())
{
temp = NULL;
}

}

}

1 Queue

void print(Node root){

if(root != null){

LinkedList queue = new LinkedList();
queue.add(root);
int level = 0
queue.add(new Integer(level++));

while(!queue.isEmpty()){

if(queue.peek() instanceof Node){

Node n = (Node)queue.pop();

for(Node child:n.getChildren())
queue.add(child);

System.out.print("-"+n.data+"-");

}else{

Integer i = (Integer)queue.pop();

System.out.println("-Finished Line: "+i)

if(!queue.isEmpty())
queue.add(new Integer(level++));
}
}
}

}

I think a similar question has been answered elsewhere in this site. The simple approach would be use a dummy node to differentiate between levels.

It's like BFS, but use two Queues to determine the end of each level

public void printInLevelOrder (){
		Queue <Node> queue = new LinkedList <Node> ();
		Queue <Node> temp = new LinkedList <Node> (); 
		queue.add(root);
		
		while (!queue.isEmpty()){
			Node cur = queue.poll();
			System.out.println(cur.value);
			if (cur.left!=null){
				temp.add(cur.left);
			}
			if (cur.right!=null){
				temp.add(cur.right);
			}
			
			if (queue.isEmpty ()){
				System.out.println("new level");
				while (!temp.isEmpty()){
					queue.add(temp.poll());
				}
				
			}

		}

	}

void BinaryTreeNode::PrintTree()
{
std::stack<BinaryTreeNode *> s;
BinaryTreeNode *curr;

s.push(this);
s.push(NULL);

while (!s.empty()) {
curr = s.top();
s.pop();
if (curr == NULL) {
printf("\n");
if (!s.empty()) {
s.push(NULL);
}
} else {
printf("%d ", curr->data);
if (curr->left != NULL) s.push(curr->left);
if (curr->right != NULL) s.push(curr->right);
}
}
}

void BinaryTreeNode::PrintTree()
{
	std::stack<BinaryTreeNode *> s;
	BinaryTreeNode *curr;

	s.push(this);
	s.push(NULL);

	while (!s.empty()) {
		curr = s.top();
		s.pop();
		if (curr == NULL) {
			printf("\n");
			if (!s.empty()) {
				s.push(NULL);
			}
		} else {
			printf("%d ", curr->data);
			if (curr->left != NULL) s.push(curr->left);
			if (curr->right != NULL) s.push(curr->right);
		}
	}
}

//C# 
using System;
using System.Collections;

class Node
{
    public int value;
    public Node leftNode;
    public Node rightNode;
    public Node(int _value)
    {
        value = _value;
    }
}

class BinarySearchTree
{
    Node rootNode;
    Queue[] printQueue;

    public BinarySearchTree(int _value)
    {
        rootNode = new Node(_value);
    }

    public void add(int _value)
    {
        addRec(rootNode, _value);
        printQueue = new Queue[maxDepth(rootNode)];
        for (int i = 0; i < maxDepth(rootNode); i++)
        {
            printQueue[i] = new Queue();
        }
    }

    public void addRec(Node _node, int _value)
    {
        if (_node == null) return;

        if (_value < _node.value)
        {
            addRec(_node.leftNode, _value);
            if (_node.leftNode == null)
            { _node.leftNode = new Node(_value); }

        }
        else if (_value >= _node.value)
        {
            addRec(_node.rightNode, _value);
            if (_node.rightNode == null)
            {
                _node.rightNode = new Node(_value);
            }
        }
    }

    public void print()
    {
        printQueue[0].Enqueue(rootNode.value);
        BreadthFirst(rootNode, 1);

        for (int i = 0; i < printQueue.Length; i++)
        {
            while (printQueue[i].Count != 0)
            {
                Console.Write(printQueue[i].Dequeue());
            }
            Console.WriteLine();
        }
    }

    public void BreadthFirst(Node _node, int _level)
    {
        if (_node == null) { return; }
        if (_node.leftNode != null)
        {
            printQueue[_level].Enqueue(_node.leftNode.value);
        }
        if (_node.rightNode != null)
        {
            printQueue[_level].Enqueue(_node.rightNode.value);
        }
        ++_level;
        BreadthFirst(_node.leftNode, _level);
        BreadthFirst(_node.rightNode, _level);
    }

    public int maxDepth(Node root)
    {
        if (root == null) { return 0; }

        return 1 + Math.Max(maxDepth(root.leftNode), maxDepth(root.rightNode));
    }

}

class Program
{
    static void Main(string[] args)
    {
        BinarySearchTree myTree = new BinarySearchTree(6);
        myTree.add(4);
        myTree.add(5);
        myTree.add(8);
        myTree.add(2);
        myTree.add(9);
        myTree.add(11);
        myTree.add(10);
        myTree.print();
        Console.Read();
    }
}

#include <stdio.h>
#include <malloc.h>

struct node {
struct node *left;
int data;
struct node *right;
};
int countwtf =0;
struct node * pop();
void push(struct node *);
void levelorder(struct node *);
void insert(struct node **,int);

struct node *queue[30];
top = -1;
void main()
{

struct node *root=NULL;
insert(&root,10);
insert(&root,6);
insert(&root,13);
insert(&root,2);
insert(&root,12);
insert(&root,5);
insert(&root,14);
insert(&root,1);
insert(&root,8);
levelorder(root);

}

void levelorder(struct node *root)
{    int height=0;
     push(root);
     while(top!=-1)//empty queue impies no nodes at the level
     { int nodeatlevel = top+1 ; 
        /* no of nodes at current level */
        
        //this while loop prints all nodes in current level
        while(nodeatlevel>0)
        {root=pop();
        printf("%d\t",root->data);
       /* we push nodes into queue to visit them in next level*/
        push(root->left);
        push(root->right) ; 
        nodeatlevel --;
        }
        height++; /*after all nodes of level are printed we increment its height */
        printf("\n");
    }
    printf("height is %d",height);
}

struct node * pop()
{struct node *temp = queue[0];
int i=1;
    while(i<=top)
    {
        queue[i-1]=queue[i]; i++;
    }top--;return temp;
};

void push(struct node *p)
{
    if(p!=NULL)
     queue[++top]=p;
}

//inserts nodes in a BST
void insert(struct node **rt,int num)
{
    if(*rt == NULL)
    {
    *rt = (struct node *)malloc(sizeof(struct node));
    (*rt)->data = num;
    (*rt)->left=NULL;
    (*rt)->right = NULL;
    return;}

    if(num<((*rt)->data))
    insert(&((*rt)->left),num);


    if(num>((*rt)->data))
    insert(&((*rt)->right),num);

}