CareerCup

private static void levelOrderTraversal(BinaryTreeNode root) {
		BinaryTreeNode temp;
		Queue<BinaryTreeNode> q = new LinkedBlockingDeque<BinaryTreeNode>();
		q.add(root);
		q.add(new BinaryTreeNode(-1));
		while (!q.isEmpty()) {
			temp = q.poll();
			
			if (temp.getData() == -1) {
				System.out.println();
				if (!q.isEmpty())
					q.add(new BinaryTreeNode(-1));

			} else {
				System.out.print(temp.getData());
				if (temp.getLeft() != null)
					q.add(temp.getLeft());
				if (temp.getRight() != null)
					q.add(temp.getRight());
			}
		}

	}

/*
Here is my take with C program.
1
/\
35
/\\
2 47
/\\
9 68

===========
Expected Output:
1
35
247
968
*/
#include <stdio.h>
#include <stdlib.h>

#define LCHILD 1
#define RCHILD 0

typedef struct Tree {
	int item;
	struct Tree *lchild;
	struct Tree *rchild;
} node;

node * createNode(int item) {
	node * newnode = (node *) malloc(sizeof(node));
	newnode->lchild = NULL;
	newnode->rchild = NULL;
	newnode->item = item;
	return newnode;
}

typedef struct Treenodelist {
	node * current;
	struct Treenodelist * next;
} nodelist;

static nodelist *head, *tail;

nodelist * enqueue(node *n) {
	nodelist *temp = (nodelist *) malloc(sizeof(nodelist));
	temp->current = n;
	temp->next = NULL;

	if (tail == NULL) {
		tail = temp;
		return tail;
	}
	while (tail->next != NULL) {
		tail->next = tail;
	}
	tail->next = temp;

	return tail->next;
}
node* dequeue() {
	if (head == NULL) {
		return NULL;
	}
	nodelist * temp=head;
	head=head->next;
	return temp->current;
}

void printTree(node *n) {
	if (n == NULL) {
		return;
	}
	tail = NULL;
	tail = enqueue(n);
	head = tail;
	node * m1 = createNode(-1);
	tail = enqueue(m1);
	while (head != NULL) {
		node *temp;
		temp = dequeue();
		if (temp->item == -1) {
			printf("\n");
			if (head != NULL) {
				tail = enqueue(m1);
			}
		}
		else {
			printf("%d", temp->item);
			if (temp->lchild != NULL) {
				tail = enqueue(temp->lchild);
				if (head == NULL)  head = tail;
			}
			if (temp->rchild != NULL) {
				tail = enqueue(temp->rchild);
				if (head == NULL)  head = tail;
			}
		}
	}
}

int main() {
	node * n1 = createNode(1);
	node * n2 = n1->lchild = createNode(3);
	node * n3 = n1->rchild = createNode(5);
	node * n4 = n2->lchild = createNode(2);
	node * n5 = n2->rchild = createNode(4);
	node * n6 = n3->rchild = createNode(7);
	node * n7 = n4->lchild = createNode(9);
	node * n8 = n4->rchild = createNode(6);
	node * n9 = n5->rchild = createNode(8);

	printTree(n1);

	return 0;
}

Simple O(n) complexity, O(n) non-recursive BFS traversal:

public void printTree(Node root){
    if(root == null){
        return;
    }
    LinkedList<Node> list = new LinkedList<Node>();
    LinkedList<Node> children = new LinkedList<Node>();
    LinkedList<Node> temp;
    StringBuilder line = new StringBuilder();
    Node node, child;

    list.add(root);

    while(!list.isEmpty()){
        while(!list.isEmpty()){
            node = list.removeFirst();
            line.append(node.value);
            child = node.left;
            if(child != null){
                children.add(child);
            }
            child = node.right;
            if(child != null){
                children.add(child);
            }
        }
        java.lang.System.out.println(line.toString());
        line.setLength(0);
        temp = children;
        children = list;
        list = temp;
    }
}

This is BFS solution. Traverse the tree by each level and queue it.
In each iteration for each node in the queue, add it's children into queue, and print the node

public void print() {

        if (rootNode == null) {
            System.out.println("Tree is empty");
            return;
        }

        ArrayDeque<Node> parentQueue = new ArrayDeque<Node>();
        ArrayDeque<Node> childQueue = new ArrayDeque<Node>();
        ArrayDeque<Node> temp;

        parentQueue.add(rootNode);
        StringBuilder sb = new StringBuilder();

        while (!parentQueue.isEmpty()) {
            Node node = parentQueue.pop();
            sb.append(node.value);
            if (node.left != null) {
                childQueue.add(node.left);
            }

            if (node.right != null) {
                childQueue.add(node.right);
            }

            if (parentQueue.isEmpty()) {
                System.out.println(sb);
                sb.setLength(0);
                if (!childQueue.isEmpty()) {
                    temp = childQueue;
                    childQueue = parentQueue;
                    parentQueue = temp;
                }
            }
        }

}

This is the C++ version of solution using BFS.

#include<list>
#include<iostream>
using namespace std;
struct Node {
	int value;
	Node * left;
	Node * right;
	Node(int v):value(v),left(0), right(0){}	
};

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

int main()
{
	Node * root = new Node(1);
	Node * n3 = new Node(3);
	Node * n5 = new Node(5);
	Node * n2 = new Node(2);
	Node * n4 = new Node(4);
	Node * n7 = new Node(7);
	Node * n9 = new Node(9);
	Node * n6 = new Node(6);
	Node * n8 = new Node(8);

	root->left = n3;
	root->right = n5;
	n3->left = n2;
	n3->right = n4;
	n5->left = n7;
	n2->left = n9;
	n2->right = n6;
	n4->left = n8;

	printTree(root);
	return 1;
}

Was this in-person or a phone interview?

// C++ Print levels
// Variable count tracks the number of nodes at a specific level.
// We know that first level has count '1'
// We first process nodes at the level, and enqueue its children in the queue.
// Once we have processed all nodes at a specific level (as indicated by count == 0),
// the queue then has nodes that belong to the next level
void levels(node * n) {
  queue<node *> q;
  q.enqueue(n);
  int count = 1; // Queue has one node at this level

  while(!q.empty()) {
    node * n1 = q.top();
    if (n1->l) {
      q.enqueue(n1->l);
    }
    if (n1->r) {
      q.enqueue(n1->r);
    }
    q.dequeue();
    count--; // We processed a node, decrement count
    if (count == 0) { // count will be zero when a level is completely processed
      count = q.size(); // Get the count of node at next level
    }
  }
}

Looks like I have found a way to solve the problem using O(n). "Index" indicates the current node which I visit. NextIndex tells me at which "index" should I add the '\n'. Once I add it, I just sum the number of nodes of the current queue (because it tels me how many children are in the next level).

public static void printTree(Node root)
    {
    if(root==null) System.out.println("");
	else{
		StringBuilder builder = new StringBuilder();

		LinkedBlockingQueue<Node> queue = new LinkedBlockingQueue<Node>();
		queue.add(root);
		int index=0,nextIndex=1;
		while(!queue.isEmpty())
		{
			index++;
			Node current=queue.poll();
			
			if(current!=null)
			{
				builder.append(current.value);
				if(current.left!=null)
				{
					queue.add(current.left);
				}
				if(current.right!=null)
				{
					queue.add(current.right);
				}
			}
	
			if(index==nextIndex)
			{
			   nextIndex+=queue.size();
			   builder.append("\n");
			}
		
		}		
		System.out.println(builder.toString());
	}
}

public void printTree(Node root) {
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);

        while(!q.isEmpty()){
            int numNodesAtlevel = q.size();
            while (numNodesAtlevel > 0){
                Node a= q.poll();
                System.out.print(a.value +" ");
                if(a.left != null)
                    q.add(a.left);
                if(a.right != null)
                    q.add(a.right);

                numNodesAtlevel --;
            }

            System.out.println();
        }
    }