CareerCup

maybe an implementation of Breadth First search.

level order traversal...

BFS

void levelByLevel(node *root)
{
node *temp;
temp=new node;
temp=root;
enqueue(root);
node *t;
while((t=dequeue())!=NULL)
{
cout<<t->data;
if(t->lchild!=NULL) enqueue(t->lchild);
if(t->rchild!=NULL) enqueue(t->rchild);
}
}

How about the following one? it seems OK.

public static void createLink(Node r)
{
	queue<Node> q=new LinkedList<Node>();	
	ArrayList<ArrayList<Node> > v=new <ArrayList<Node> >();
	ArrayList<Node> l=new ArrayList<Node>();	
	q.add(r);	
	int level=1;
	int num=0;	
	
	while(!q.isEmpty)
	{
		if(level>0)
		{
			Node p=q.remove();
			l.add(p);
			level--;
			if(p.left!=null)
			{	
				q.add(p.left);
				num++;
			}
			if(p.right!=null)
			{	
				q.add(p.right);
				num++;
			}
		}
		else if(level==0)
		{
			v.add(l);
			level=num;
			ArrayList<Node> l=new ArrayList<Node>();
		}
	}
}

simple level order traversal dude. WTH!

I haven't read through the code above thoroughly but I'm pretty sure simple bfs using a queue or stack won't work. The point is, how do you know when you have changed levels?? When you pop a node off your queue there is no way of knowing what level it came from unless you explicitly keep a level field in the node. I will give the guys at Amazon some credit and assume that this isn't allowed - or at least isn't the solution they are looking for!

A better solution is fairly simple. Keep 2 queues, one for the current layer and one for the next. Pop nodes from the Current queue, print their details (no newline!) and add their children to the Next queue. When the Current queue is empty print a newline, assign the Current pointer to the Next queue, and assign the Next pointer to a new queue. The outer and inner loops have the same condition, that the Current queue is not empty. When this breaks on the outer loop it means the Next queue was empty before reassignment to Current - ie there were no more children.

<pre lang="" line="1" title="CodeMonkey60265" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}

</pre><pre title="CodeMonkey60265" input="yes">
</pre>

Based on comment from "anon on July 13, 2011 " here solution for Java:

public void traverseLayers(LevelTraverseExecutor<T> executor) {
		java.util.Deque<Node<T>> deque = new LinkedList<Node<T>>();
		java.util.Deque<Node<T>> childDeque = new LinkedList<Node<T>>();
		deque.addLast(root);
		int level = 0;
		while (!deque.isEmpty()) {
			Node<T> node = deque.pop();
			System.out.println(node.value);
			if (node.left != null) {
				childDeque.addLast(node.left);
			}
			if (node.right != null) {
				childDeque.addLast(node.right);
			}

			if (deque.isEmpty()) {
				System.out.println("new Level: " + ++level);

				// swap queues
				java.util.Deque<Node<T>> tmp = deque;
				deque = childDeque;
				childDeque = tmp;
			}
		}
	}