CareerCup

Two steps:
(1)link each node with its next sibling(leftest sibling).
(2)print each level's nodes by finding the leftest node of each level then print all its siblings.
Code in C++:

void specificBFS(Node* root)
{
	if(root == NULL) return;
	//link every node with its leftest sibling
	root->foo = NULL;
	linkSibling(root);
	//print from leftest node of each level to all its siblings
	for(Node* p = root; p != NULL; ){
		printSiblings(p);
		if(p->left != NULL) p = p->left;
		else if(p->right != NULL) p = p->right;
		else p = findFirstNephew(p);
	}
}
void linkSibling(Node* p)//p has already linked with its next sibling
{
	if(p->left != NULL && p->right != NULL){
		p->left->foo = p->right;
		p->right->foo = findFirstNephew(p);
		//here link right child with its sibling first
		linkSibling(p->right);
		linkSibling(p->left);
	}
	else if(p->left != NULL){
		p->left->foo = findFirstNephew(p);
		linkSibling(p->left);
	}
	else if(p->right != NULL){
		p->right->foo = findFirstNephew(p);
		linkSibling(p->right);
	}
}
Node* findFirstNephew(Node* p)//find the leftest nephew
{
	for(Node* sibling = p->foo; sibling != NULL; sibling = sibling->foo){
		if(sibling->left != NULL) return sibling->left;
		if(sibling->right != NULL) return sibling->right;
	}
	return NULL;
}
void printSiblings(Node* p)//print all p's siblings
{
	for(; p != NULL; p = p->foo) printf("%d ", p->data);
}

Logic :
1) Start print the current node and all its siblings
2) If there is a left node , go there and print its siblings
else if it has rightnode, go there and print the siblings
3) if there is no left or right for current node, then search its siblings for one that has a left or right., Then select that node and repeat step 1)

void printfBFS (node* root) {
    if (root==NULL) return;
    node *tmp = root;
    while (tmp) {
        cout << tmp->data;
        tmp = tmp->foo;
    }
    if (root->left) printBFS (root->left);
    else if (root->right) printfBFS (root->right);
    else {
          while (root) {
             if (root->left) {
                 return printfBFS (root->left); 
                  break;
             } else if (root->right) {
                  return printfBFS (root->left); 
                  break;
              }
              root = root->foo;
         }
         return;
    }

My idea is to recursively print each level, and let the "foo" of the next level (if there is) connected. Always find the first valid node of next level for recursion. Below code is verified:

struct Node{
int data;
Node* left;
Node* right;
Node* foo;
Node(int a):left(NULL), right(NULL), data(a), foo(NULL) {}
};

void BFS(Node *root){
if(root == NULL){
return;
}
Node *start = root;
while(root != NULL){
printf("%d, ", root->data);
if(root->left != NULL){
if(root->right != NULL){
root->left->foo = root->right;
}
else{
Node *sib = root->foo;
while((sib != NULL) && (sib->left == NULL) && (sib->right == NULL)){
sib = sib->foo;
}
if(sib == NULL){
root->left->foo = NULL;
}
else if(sib->left != NULL){
root->left->foo = sib->left;
}
else{
root->left->foo = sib->right;
}
}
}
if(root->right != NULL){
Node *sib = root->foo;
while((sib != NULL) && (sib->left == NULL) && (sib->right == NULL)){
sib = sib->foo;
}
if(sib == NULL){
root->right->foo = NULL;
}
else if(sib->left != NULL){
root->right->foo = sib->left;
}
else{
root->right->foo = sib->right;
}
}
root = root->foo;
}

while((start != NULL) && (start->left == NULL) && (start->right == NULL)){
start = start->foo;
}
if(start == NULL){
return;
}
else if(start->left != NULL){
BFS(start->left);
}
else{
BFS(start->right);
}
return;
}

int _tmain(int argc, _TCHAR* argv[])
{
Node Node1(1);
Node Node2(2);
Node Node3(3);
Node Node4(4);
Node Node5(5);
Node Node6(6);
Node Node7(7);
Node Node8(8);
Node Node9(9);
Node Node10(10);
Node Node11(11);
Node Node12(12);
Node1.left = &Node2;
Node1.right = &Node3;
Node2.left = &Node4;
Node3.left = &Node5;
Node3.right = &Node9;
Node4.right = &Node6;
Node6.left = &Node7;
Node6.right = &Node8;
Node9.left = &Node10;
Node9.right = &Node11;
Node11.right = &Node12;
BFS(&Node1);
return 0;
}

void LevelWithoutQueue(struct Node *node){
if(!node)
return;
while(node){
cout<<node->data;
if(node->left){
if(!node->foo){
node->foo=node->left;
}
else{
struct Node *foo=node->foo;
while(foo && foo->foo)
foo=foo->foo;
foo->foo=node->left;
}
}
if(node->right){
if(!node->foo){
node->foo=node->right;
}
else{
struct Node *foo=node->foo;
while(foo && foo->foo)
foo=foo->foo;
foo->foo=node->right;
}
}
node=node->foo;
}
}

Dudes here is the algo:-
Lets assume we have exposed two methods on node with name first and second.

node.first => if node has left child return it otherwise return right child
node.second => if node has right child return it otherwise return left child

The call below recursive function

Node connect(root){
if node.right == null && node.left == null
return root
node.left.foo = node.right.foo
node.left.second = node.right.first
connect(root.left)
connect(root.right)
return root;
}

Of-course you need to take care of some null cases in above algo. Implementing NULL pattern on node would make it easier to handle null cases.

And now print all levels, as they are already connected so it can be printed without any trouble.

Space complexity - O(h), where h is the height of the tree.
Time complexity - O(n), n is no of nodes

Feel free to point out any correction.

Solution:
Given 'foo' of a node points to its adjacent/sibling node (all nodes at same depth).
Logic is to loop until all the siblings are visited( All nodes on same depth level).
Move to the next depth level by moving to next left node.

public static void printBFS(Node<?> root){
		if(root != null){
			Node<?> temp = root;
			while(temp != null){
				System.out.print(temp.data+" - ");
				temp = temp.getFoo();
			}
			if(root.getLeft() != null){
				printBFS(root.getLeft());
			}
			
		}
	}

Here is the complete implementation,

public class LevelOrder {

	/**
	 * @param args
	 */
	static class Node<T>{
		Node<?> left,right,foo;
		T data;
		
		Node(T val){
			data = val;
		}
		
		/**
		 * @return the left
		 */
		public Node<?> getLeft() {
			return left;
		}
		
		/**
		 * @return the right
		 */
		public Node<?> getRight() {
			return right;
		}
		/**
		 * @return the foo
		 */
		public Node<?> getFoo() {
			return foo;
		}
		/**
		 * @param left the left to set
		 */
		public void setLeft(Node<?> left) {
			this.left = left;
		}
		/**
		 * @param right the right to set
		 */
		public void setRight(Node<?> right) {
			this.right = right;
		}
		/**
		 * @param foo the foo to set
		 */
		public void setFoo(Node<?> foo) {
			this.foo = foo;
		}
		
	}
	
	public static void printBFS(Node<?> root){
		if(root != null){
			Node<?> temp = root;
			while(temp != null){
				System.out.print(temp.data+" - ");
				temp = temp.getFoo();
			}
			if(root.getLeft() != null){
				printBFS(root.getLeft());
			}
			
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Node<Integer> one = new Node<Integer>(20);
		Node<Integer> two = new Node<Integer>(10);
		Node<Integer> three = new Node<Integer>(25);
		Node<Integer> four = new Node<Integer>(7);
		Node<Integer> five = new Node<Integer>(15);
		Node<Integer> six = new Node<Integer>(22);
		Node<Integer> seven = new Node<Integer>(5);
		Node<Integer> eight = new Node<Integer>(21);
		Node<Integer> nine = new Node<Integer>(24);
		Node<Integer> ten = new Node<Integer>(17);
		Node<Integer> eleven = new Node<Integer>(28);
		
		one.setLeft(two);
		one.setRight(three);		
		two.setLeft(four);
		two.setRight(five);
		three.setLeft(six);
		three.setRight(eleven);
		four.setLeft(seven);
		five.setRight(ten);
		six.setLeft(eight);
		six.setRight(nine);
		
		one.setFoo(null);
		two.setFoo(three);
		four.setFoo(five);
		five.setFoo(six);
		six.setFoo(eleven);
		seven.setFoo(ten);
		ten.setFoo(eight);
		eight.setFoo(nine);
		
		printBFS(one);
		
	}

}