CareerCup

struct List* Result[] //array for holding LinkList at each level
int i //index for Result for each level
void LevelOrderList(struct Node * root)
{
struct Node* Temp;
if(!root)
return;
Struct Queue* Q=CreateQue();
Enque(Q,root);
Enque(Q,NULL);
while(IsQueEmty())//return 1 if not empty else 0
{
Temp=Deque();
if(Temp==NULL) //one level done so create marker for other level
{
Enqueue(Q,NULL);
i++;
}
else
{
if(Temp->left)
Enqueue(Temp->left);
if(Temp->Right)
Enqueue(Temp->Right);
CreateLinkList(Result[i],Temp->data);
}
}

Implement The Function CreateLinkList as simple LinkList Insertion Program.

we can use breadth first search algorithm

follow the link

#include<queue>
#include<algorithm>
#include<vector>


vector<vector<BTNode*> >& result level_wise_list_bst(BTNode* root) {
	if(NULL == root) return NULL;
	
	vector<vector<BTNode*> > result;
	queue<BTNode*> q;
	q.push(root);
	
	int curr_level_node_count = 1;
	int next_level_node_count = 0;
	int curr_level = 0;
	
	while(false == q.empty() )
	{
		BTNode* curr_node = q.pop();
		result[curr_level].push_back(curr_node);
		curr_level_node_count--;
		
		if(curr_node->left) {
			q.push_back(curr->left);
			next_level_node_count++;
		}
		if(curr_node->right) {
			q.push_back(curr->right);
			next_level_node_count++;
		}
		
		if( curr_level_node_count == 0 ) {
			curr_level++;
			swap(curr_level_node_count, next_level_node_count);
		}

	}
	
	return result;
}

Is the given Tree BST in the question? The Tree doesn't satisfy BST properties.
It's not clear. Plz., recheck guys before giving answers.

public static ArrayList<ArrayList<Integer>> createLevelArrays(BinaryTreeNode head){
if(head==null){
return null;
}
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
HashMap<BinaryTreeNode,Integer> map=new HashMap<BinaryTreeNode,Integer>();
map.put(head, 1);
Queue<BinaryTreeNode> path=new LinkedList<BinaryTreeNode>();
path.add(head);
while(!path.isEmpty()){
BinaryTreeNode current=path.poll();
int currentlevel=map.get(current);
if(result.size()<currentlevel){
result.add(new ArrayList<Integer>());
}
result.get(currentlevel-1).add(current.value);
if(current.left!=null){
map.put(current.left, currentlevel+1);
path.add(current.left);
}
if(current.right!=null){
map.put(current.right, currentlevel+1);
path.add(current.right);
}

}

return result;
}

Iterative solution: (Recursion should be avoided cause usually it gives high time complexity)

public static ArrayList<LinkedList> convert(Node root){		
		ArrayList<LinkedList> result = new ArrayList<LinkedList>();
		ArrayList<Node> queue = new ArrayList<Node>();
		
		queue.add(root);
		
		while(!queue.isEmpty()){
			ArrayList<Node> tempQueue = new ArrayList<Node>();
			
			for(Node tmp: queue){
				tempQueue.add(tmp);
			}
			
			queue.removeAll(queue);
			
			LinkedList<Integer> list = new LinkedList<Integer>();
			
			for(Node n: tempQueue){
				if(n.hasLeft()){
					queue.add(n.left);
				}
				if(n.hasRight()){
					queue.add(n.right);
				}
				
				list.add(new Integer(n.value));				
			}
			result.add(list);
		}
		return result;		
	}

Hope this problem needs extra space to solve ... I mean you need a stack or queue in addition to the final set of linked lists. Please let me know in case I am wrong.

Solution - Do level order traversal and push all elements in the next level into the stack or queue. And build a linked list with the elements in the current level(these elements are got by poping the stack/queue). Initially, for the first level, the element is got from the pointer to the root of the tree. Do this till end of the final level of the tree.

public static ArrayList<LinkedListNode<Integer>> constructLinkedListForEachLevel(BinaryTreeNode<Integer> root){

        if (root == null) {
            return null;		
        }		
        Queue<BinaryTreeNode<Integer>> pendingNodes = new LinkedList<BinaryTreeNode<Integer>>();		
        pendingNodes.add(root);				
        int currentLevelRemaining = 1;	    
        int nextLevelCount = 0;	    		
        LinkedListNode<Integer> currentLevelHead = null;		
        LinkedListNode<Integer> currentLevelTail = null;		
        ArrayList<LinkedListNode<Integer>> output = new ArrayList<>();		
        while (!pendingNodes.isEmpty()) {
            BinaryTreeNode<Integer> currentNode;				
            currentNode = pendingNodes.remove();				
            LinkedListNode<Integer> newNode = new LinkedListNode<Integer>(currentNode.data);				
            if (currentLevelHead == null) {					
                currentLevelHead = newNode;
                currentLevelTail = newNode;
            }
            else {
                currentLevelTail.next = newNode;
                currentLevelTail = newNode;
            }
            if (currentNode.left != null) {
                pendingNodes.add(currentNode.left);
                nextLevelCount++;
            }
            if (currentNode.right != null) {
                pendingNodes.add(currentNode.right);
                nextLevelCount++;
            }	
            currentLevelRemaining--;
            if (currentLevelRemaining == 0) {
                output.add(currentLevelHead);
                currentLevelHead = null;
                currentLevelTail = null;
                currentLevelRemaining = nextLevelCount;
                nextLevelCount=0;
            }
        }
        return output;
    }
}

public static ArrayList<LinkedListNode<Integer>> constructLinkedListForEachLevel(BinaryTreeNode<Integer> root){
		// Write your code here
        if (root == null) {
            return null;		
        }		
        Queue<BinaryTreeNode<Integer>> pendingNodes = new LinkedList<BinaryTreeNode<Integer>>();		
        pendingNodes.add(root);				
        int currentLevelRemaining = 1;	    
        int nextLevelCount = 0;	    		
        LinkedListNode<Integer> currentLevelHead = null;		
        LinkedListNode<Integer> currentLevelTail = null;		
        ArrayList<LinkedListNode<Integer>> output = new ArrayList<>();		
        while (!pendingNodes.isEmpty()) {
            BinaryTreeNode<Integer> currentNode;				
            currentNode = pendingNodes.remove();				
            LinkedListNode<Integer> newNode = new LinkedListNode<Integer>(currentNode.data);				
            if (currentLevelHead == null) {					
                currentLevelHead = newNode;
                currentLevelTail = newNode;
            }
            else {
                currentLevelTail.next = newNode;
                currentLevelTail = newNode;
            }
            if (currentNode.left != null) {
                pendingNodes.add(currentNode.left);
                nextLevelCount++;
            }
            if (currentNode.right != null) {
                pendingNodes.add(currentNode.right);
                nextLevelCount++;
            }	
            currentLevelRemaining--;
            if (currentLevelRemaining == 0) {
                output.add(currentLevelHead);
                currentLevelHead = null;
                currentLevelTail = null;
                currentLevelRemaining = nextLevelCount;
                nextLevelCount=0;
            }
        }
        return output;
    }
}