CareerCup

Use an indicator node for the end of one level

here is the solution i proposes to the interviewer and he was happy at single shot...

take two ques Q1, Q2
//each time in any ques only the nodes belong to one level will be present
//hence print all the que nodes and print new line
enque root into Q1

while Q1!=empty
print node->data and enque the childs of all nodes in Q2

print("\n");
now process Q2,
while Q2!=empty
print node->data;
enque childs of each node in Q1.

print("\n");

if(Q1.empty() and Q2.empty())
break;//we have processes whole tree.

We can traverse the tree and store the data and the level in a 2-D array.

Now accessing the array is a simple step

Space complexity : O(n2) [This can be compressed by using a 2-D list instead of predefined array].
Time Complexity : O(n)

I Solved the problem like this ,i used right sibling representation so that each node does not have store information about all its childs
1
\
2 -> 3 ->4
\ \
5->6 7->8
\
9
we are supposed to print
1
234
5678
9
I used q Queue[][] with Level information , traversed the complete tree and loaded the queue ,once done i print the nodes level wise , let me know if my approach is better or not ?

Interviewer first asked to come up with a Data structure , then i suggested the right Sibling approach tree structure . Other DS i can think of is Node where it stores all its childs in a linked list of nodes ... i feel first DS i used more better.

@ibnipun10
Space Complexity is 2(N) right instead N2 , we are using a double dimensional array .

I solved this problem and wrote code for it and answered some general questions on binary search trees and trees , interview went for a hour , they said they will get back with in two days , does it mean i am rejected ?

Here is sample java programme for level order tree traversal.


package tree;

import java.util.List;

import sun.misc.Queue;


public class NTreeTraversal {

Queue traversalQueue = new Queue();

public void nTreeTraversal(NTreeNode root) throws InterruptedException{
if(root==null){
return;
}
System.out.println("Label Order tree traversal is -> ");
traversalQueue = new Queue();

traversalQueue.enqueue(root);
NTreeNode ptr = (NTreeNode) traversalQueue.dequeue();
while(ptr !=null){

System.out.println(ptr.getValue() + " \n");
addDirectChildInQueue(ptr);
ptr = (NTreeNode) traversalQueue.dequeue();

}
}

private void addDirectChildInQueue(NTreeNode node){
if(node == null){
return;
}
List<NTreeNode> directChildNodes = null;
NTreeNode ptr = node.getChild();
while(ptr !=null){
traversalQueue.enqueue(ptr);
ptr= ptr.getSibling();
}
}

public static void main(String args[]){

NTreeNode treeNode1 = new NTreeNode("1", null, null);
NTreeNode treeNode2 = new NTreeNode("2", null, null);
NTreeNode treeNode3 = new NTreeNode("3", null, null);

NTreeNode treeNode4 = new NTreeNode("4", null, null);
NTreeNode treeNode5 = new NTreeNode("5", null, null);
NTreeNode treeNode6 = new NTreeNode("6", null, null);
NTreeNode treeNode7 = new NTreeNode("7", null, null);
NTreeNode treeNode8 = new NTreeNode("8", null, null);

treeNode1.setChild(treeNode2);
treeNode2.setChild(treeNode5);
treeNode2.setSibling(treeNode3);
treeNode3.setChild(treeNode8);
treeNode3.setSibling(treeNode4);
treeNode5.setSibling(treeNode6);
treeNode6.setSibling(treeNode7);
NTreeTraversal ntreeTraversal = new NTreeTraversal();

try {
ntreeTraversal.nTreeTraversal(treeNode1);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}

}

<pre lang="c++" line="1" title="CodeMonkey94755" class="run-this">#include <iostream>

using namespace std;

int main() {

queue<node> q;
int current_level = 0;
int next_level = 0;
q.push(root);
current_level=1;
while(!q.empty())
{
if(current_level == 0){
current_level = next_level;
next_level = 0;
cout<<"\n";
}
node temp = q.front();
for each child of temp{
q.push(child);
next_level++;
}
cout<<temp->data;
q.pop();
current_level--;
}



}
</pre><pre title="CodeMonkey94755" input="yes">
</pre>

yeah, one queue should do. Do a regular level order traversal with a single modification - when you have inserted all the children of a node, at the end insert a NULL to indicate level has to be changed.

What's a Developer Program Engineer?

you can do it without storing any auxiliary storage.

Hi, how about this code, just get ideas from "cracking the coding".

class Node
{
	int value;
	Node first;
	Node next;
	Node(...)
	{
		...
	}
}

public static int printEveryNode(Node root)
{
	ArrayList<LinkedList<Node>> array=new ArrayList<LinkedList<Node>>();
	LinkedList<Node> link=new LinkedList<Node>();
	link.add(root);
	int level=0;
	array.add(level,link);
	

	while(true)
	{
		link=new LinkedList<Node>();
		for(int i=0;i<array.get(level).size();i++)
		{	
			Node n=array.get(level).get(i).first;	
			if(n)
			{
				print(n.value);
				link.add(n);
				while(n.next)
				{	
					Node m=n.next;
					link.add(m);
					print(m.value);
				}
			}
			
		}
		level++;
		array.add(level, link);
		print("*********************************");
		
	}
	
}

You can check my implementation here:

leniel.net/2011/11/nary-tree-graph-traversal-level-by.html