iLabs Interview Question
Software Engineer / DevelopersCountry: 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