CareerCup

Breadth-first search algorithm using a dummy Node to divide each level (may not be necessary if we keep track of each level in a different way )
But this works just fine.

public static List<List<TNode>> treeToLinkList(TNode node){
		List<List<TNode>> result = new LinkedList<List<TNode>>();
		List<TNode> level = new LinkedList<TNode>();
		Queue<TNode> queue = new LinkedList<TNode>();
		TNode dummy = new TNode(-1);  // this is a dummy node that will divide each level on the tree
		
		// Special case for Root
		level.add(node);
		result.add(level);
		level = new LinkedList<TNode>();
		queue.add(node);
		queue.add(dummy);
		
		while(queue.size() > 1){  // The last element will be the dummy node
			TNode current = queue.poll();
			
			if(current == dummy){ // at this point we have reach the end of a level.
				if(level != null){
					result.add(level);
				}
				level = new LinkedList<TNode>();
				queue.add(dummy); // add a dummy to divide the level
			}else{
				
				if(current.left != null){
					queue.add(current.left);
					level.add(current.left);
				}
				if(current.right != null){
					queue.add(current.right);
					level.add(current.right);
				}
			}
		}
		return result;
		
	}
	
	static class TNode{
		public TNode left;
		public TNode right;
		public int value;
		public TNode(int val){
			this.value = val;
		}
	}

Test case:

TNode root = null;
		root = insert(root,100);
		insert(root,200);
		insert(root,50);
		insert(root,25);
		insert(root,75);
		insert(root,250);
		insert(root,150);
		insert(root,10);
		insert(root,8);
		insert(root,6);
		insert(root,4);
		insert(root,300);
		insert(root,400);
		insert(root,500);

List<List<TNode>> result = treeToLinkList(root);
		for(List<TNode> l : result){
			for(TNode n: l){
				System.out.print("->" + n.value);
			}
			System.out.println();
		}

Output:

->100
->50->200
->25->75->150->250
->10->300
->8->400
->6->500
->4

How about this:

bfs(v)
{
  Q = {v, dummy};

  l = new list;
  while (Q.size != 1) { // while Q does not contain any real vertex
    v = Q.pop_front();  // remove the first node in the queue
    if (v == dummy) {
       output the list, and then clear it;
       Q.push_back(dummy);
       continue;
    }

    l.insert(v);
   
    for (each child of v) 
      Q.push_back(v);
}

We can do an in-order traversal while maintaining the current depth so that we know to which list to add the current node. If we've never seen the current depth before, add a new list.

private void getNodesByDepthHelper (TreeNode root, int currentDepth, ArrayList<LinkedList<TreeNode>> depthLists)
{
    if (root == null) { return; }

    if (depthLists.size() == currentDepth)
    {
        depthLists.add (new LinkedList<TreeNode> ());
    }
    getNodesByDepthHelper (root.left, currentDepth+1, depthLists);
    depthBuckets.get(currentDepth).add(root);
    getNodesByDepthHelper (root.right, currentDepth+1, depthLists);
}

public ArrayList<LinkedList<TreeNode>> getNodesByDepth(TreeNode root)
{
    ArrayList<LinkedList<TreeNode>> depthLists = new ArrayList<LinkedList<TreeNode>> ();
    getNodesByDepthHelper (root, 0, depthLists);
    return depthLists;
}