## iLabs Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**Phone Interview

my solution was

void printLevelOrder(struct node* root)

{

int h = height(root);

int i;

for(i=1; i<=h; i++)

printGivenLevel(root, i);

}

void printGivenLevel(struct node* root, int level)

{

if(root == NULL)

return;

if(level == 1)

printf("%d ", root->data);

else if (level > 1)

{

printGivenLevel(root->left, level-1);

printGivenLevel(root->right, level-1);

}

}

what will be complexity in case of balance binary tree .

in worst case it will be O(n)

I think the simplest way is to do it iteratively rather than recursively. In pseudo-code:

```
Set <Node> nodesToVisit = new HashSet();
nodesToVisit.add(root);
int levelAt = 0;
while(nodesToVisit.size() != 0)
{
Set <Node> nextNodesToVisit = new HashSet();
for(Node node : nodesToVisit)
{
System.out.print(node.getValue() + ", ");
if(node.hasLeft())
nextNodesToVisit.add(node.getLeft());
if(node.hasRight())
nextNodesToVisit.add(node.getRight());
}
System.out.println();
nodesToVisit = nextNodesToVisit;
}
```

here you go:

```
public void TraverseNode(Node node)
{
Queue<Node> queue = new Queue<Node>();
if (node == null)
return;
int nodesInCurrentLevel = 1; int nodesInNextLevel = 0;
queue.Enqueue(node);
while (queue.Count > 0)
{
Node nodeToTraverse = queue.Dequeue();
if (nodeToTraverse.Left != null)
{
queue.Enqueue(nodeToTraverse.Left); nodesInNextLevel++;
}
if (nodeToTraverse.Right != null)
{
queue.Enqueue(nodeToTraverse.Right); nodesInNextLevel++;
}
Console.Write(nodeToTraverse.Data);
nodesInCurrentLevel--;
if(nodesInCurrentLevel == 0)
{
Console.WriteLine();
nodesInCurrentLevel = nodesInNextLevel;
nodesInNextLevel = 0;
}
}
}
```

And since you have to print each node, you have to traverse each node and you always do that so the complexity will be O(n).

i am not looking for other solutions plese tell complexity for solutions i given........

```
public static void printLevel(Node root)
{
if(root==null)
return;
Queue q=new Queue();
q.enqueue(root);
q.par_num++;
while(q.size()>0)
{
Node temp=q.dequeue();
if(temp.left!=null)
q.enqueue(temp.left);
if(temp.right!=null)
q.enqueue(temp.left);
if(q.par_num==0)
q.printQueue();
q.par_num=q.child_num;
q.child_num=0;
}
}
class Queue
{
LinkedList<Node> list;
int child_num, par_num;
Queue()
{
list=new LinkedList<Node>();
child_num=0;
par_num=0;
}
public void enqueue(Node item)
{
child_num++;
list.addLast(item);
}
public Node dequeue()
{
par_num--;
if(list.size()==0)
return null;
else
return list.removeFirst();
}
public int size()
{
return list.size();
}
public void printQueue()
{
System.out.println();
for(int i=0;i<list.size();i++)
{
Node temp=list.get(i);
System.out.print(temp.value);
}
}
}
class Node
{
Node left;
Node right;
int value;
Node(Node left, Node right, int value)
{
this.left=left;
this.right=right;
this.value=value;
}
}
```

- siva.sai.2020 April 02, 2013