Engineering Questions with Answers - Multiple Choice Questions

# Data Structure MCQ – Inorder Traversal

1 - Question

For the tree below, write the in-order traversal.

a) 6, 2, 5, 7, 11, 2, 5, 9, 4
b) 6, 5, 2, 11, 7, 4, 9, 5, 2
c) 2, 7, 2, 6, 5, 11, 5, 9, 4
d) 2, 7, 6, 5, 11, 2, 9, 5, 4

Explanation: In-order traversal follows LNR(Left-Node-Right).

2 - Question

For the tree below, write the level-order traversal.

a) 2, 7, 2, 6, 5, 11, 5, 9, 4
b) 2, 7, 5, 2, 11, 9, 6, 5, 4
c) 2, 5, 11, 6, 7, 4, 9, 5, 2
d) 2, 7, 5, 6, 11, 2, 5, 4, 9

Explanation: Level order traversal follows a breadth first search approach.

3 - Question

Select the code snippet which performs in-order traversal.
a)

```public void inorder(Tree root)
{
System.out.println(root.data);
inorder(root.left);
inorder(root.right);
}```

b)

```public void inorder(Tree root)
{
inorder(root.left);
System.out.println(root.data);
inorder(root.right);
}```

c)

```public void inorder(Tree root)
{
System.out.println(root.data);
inorder(root.right);
inorder(root.left);
}```

d)

```public void inorder(Tree root)
{
inorder(root.right);
inorder(root.left);
System.out.println(root.data);
}```

Explanation: In-order traversal follows LNR(Left-Node-Right).

4 - Question

Select the code snippet which performs level-order traversal.
a)

```public static void levelOrder(Tree root)
{
while(!queue.isEmpty())
{
Node tempNode=queue.poll();
System.out.println("%d ",tempNode.data);
if(tempNode.left!=null)
if(tempNode.right!=null)
}
}```

b)

```public static void levelOrder(Tree root)
{
while(!queue.isEmpty())
{
Node tempNode=queue.poll();
System.out.println("%d ",tempNode.data);
if(tempNode.left!=null)
if(tempNode.right!=null)
}
}```

c)

```public static void levelOrder(Tree root)
{
while(!queue.isEmpty())
{
Node tempNode=queue.poll();
System.out.println("%d ",tempNode.data);
if(tempNode.right!=null)
if(tempNode.left!=null)
}
}```

d)

```public static void levelOrder(Tree root)
{
while(!queue.isEmpty())
{
Node tempNode=queue.poll();
System.out.println("%d ",tempNode.data);
if(tempNode.right!=null)
if(tempNode.left!=null)
}
}```

Explanation: Firstly add the root node to the queue. Then for all the remaining nodes, pop the front end of the queue and print it, add the left and right children of the popped node to the queue.

5 - Question

What is the space complexity of the in-order traversal in the recursive fashion? (d is the tree depth and n is the number of nodes)
a) O(1)
b) O(nlogd)
c) O(logd)
d) O(d)

Explanation: In the worst case we have d stack frames in the recursive call, hence the complexity is O(d).

6 - Question

What is the time complexity of level order traversal?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)

Explanation: Since you have to go through all the nodes, the complexity becomes O(n).

7 - Question

Which of the following graph traversals closely imitates level order traversal of a binary tree?
a) Depth First Search
c) Depth & Breadth First Search
d) Binary Search

Explanation: Both level order tree traversal and breadth first graph traversal follow the principle that visit your neighbors first and then move on to further nodes.

8 - Question

In a binary search tree, which of the following traversals would print the numbers in the ascending order?
a) Level-order traversal
b) Pre-order traversal
c) Post-order traversal
d) In-order traversal