# Data Structure Questions and Answers – Inorder Traversal

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Inorder Traversal”.

1. 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, the recursive call has d stack frames, so the complexity is O. (d).

2. What is the time complexity of level order traversal?
A) O(1)
B) O(n)
C) O(logn)
D) O(nlogn)

Explanation: Since you must traverse all of the nodes, the difficulty rises to O. (n).

3. 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 are based on the concept of first visiting your neighbours and then moving on to new nodes.

4. 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

Explanation: Since the left child of a node is always less than the node and the right child is always greater than the node in a binary search tree, an in-order traversal will print them in a non-decreasing manner.

5. 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).

6. 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: A breadth first search technique is used for level order traversal.

7. 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).

8. 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)