CareerCup

i) Have a map for Map<level, List<Node>>
ii) for each node, traverse up to root and calculate the node's level
iii) Store the node is list of corresponding level

This takes n*h where 'n' is number of nodes and 'h' is height of tree.

Iterate in below fashion and print
Repeat until there is no node in the map
For each level from level 0..size of Map-1:
print non-empty node in the current level
remove the node from list
The above loop takes n*h time complexity, where is n is number of nodes and h is height of tree.

If tree is balanced, height = logn, complexity is n*log n
if tree is skewed, height is n, complexity is n*n

public static void printTreeLayers(Node... nodes) {
		for (int i = 0; i < nodes.length; i++) {
			findNodeLayer(nodes[i]);
		}

		Map<Integer, List<Node>> layers = new HashMap<Integer, List<Node>>();
		for (Node n : map.keySet()) {
			int layer = map.get(n);
			List<Node> list = layers.get(layer);
			if (null != list) {
				list.add(n);
			} else {
				list = new LinkedList<Node>();
				list.add(n);
				layers.put(layer, list);
			}
			if (list.size() > maxSize)
				maxSize = list.size();
		}

		System.out.println(layers);
		System.out.println("max layer = " + (maxLayer + 1));
		System.out.println("max size = " + maxSize);

		for (int i = 0; i < maxSize; i++) {
			for (int j = 0; j <= maxLayer; j++) {
				List<Node> list = layers.get(j);
				int size = list.size();
				if (i < size)
					System.out.print(list.get(i) + "\t");
				else {
					System.out.print("\t");
				}
			}
			System.out.println();
		}

	}

	public static int findNodeLayer(Node node) {
		if (null == node)
			return -1;

		int ret = 0;

		if (null != node.parent) {
			ret = findNodeLayer(node.parent) + 1;
			if (ret > maxLayer) {
				maxLayer = ret;
			}
		}

		map.put(node, ret);
		return ret;
	}

Pseudo Code:

1. Create a vector<vector<int> > levelorder,2 queues of queue<Node*> q1 and q2,  counter=0
2. Add NULL pointer to q1.
3. while q1 and q2 are not empty
	while(q1 not empty)	
		current=dequeue a pointer from the q1
			iterate over the nodes in the list to find a node which has a parent as current.
			add the element to the q2 and vector
	increment counter.
	push vector to levelorder
	q1=q2; clear q2.

4. print out the vectors in round robin fashion with required output spacing.

Time Complexity: O(n*n)
Space complexity: O(n)
where n is the number of nodes in the input.

This is a brute force solution. I am sure there must a better solution to this problem.

Here is my thought.

Lets assume our list looks like this

L1 (N1 -> N2 -> N3 ...)
|
L2 (N1 -> N2 -> N3 -> N4 ...)
|
L3 (N1 -> N2 -> N3 -> N4 ...)
|
...

1. Create a vector of "List"s to store
2. Separate "List" (or layers) into individual lists. Store the 
3. Print current element from each list iteratively and advance each list by one node every time its printed.
4. If any list ends, just print empty spaces in its place till all lists end

This looks like filling the sibling pointer problem.

1. In the Tree itself add one more pointer which point to the sibling on that level.
Filling the siblings can be done in o(n) when parent pointer is given.

2. Just make the right pointers null.

3. This has the resultant as a list.

1. Go thru the list and create a map of <parent_name, List<nodes>>. Also note down the node whose parent = null while doing this. This will be the root.

2. Start with the root. Print it.
Get the list of root's children from the map. Print it.. this will be level 2.
For each child, do the same now.