Data Structure Questions and Answers – Inorder Traversal

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

1. For the tree below, write the in-order traversal.
The in-order traversal is 6, 2, 5, 7, 11, 2, 5, 9, 4 for the tree below
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
View Answer

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

2. For the tree below, write the level-order traversal.
The level-order traversal is 2, 7, 5, 2, 11, 9, 6, 5, 4 follows breadth first approach
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
View Answer

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

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

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

b)

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
public void inorder(Tree root)
{
	inorder(root.left);
	System.out.println(root.data);
	inorder(root.right);
}

c)

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

d)

advertisement
public void inorder(Tree root)
{
	inorder(root.right);
	inorder(root.left);
	System.out.println(root.data);
}
View Answer
Answer: b
Explanation: In-order traversal follows LNR(Left-Node-Right).
 
 

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

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

b)

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

c)

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

d)

public static void levelOrder(Tree root) 
{  
    Queue<Node> queue=new LinkedList<Node>();  
    queue.add(root);  
    while(!queue.isEmpty())  
    {  
        Node tempNode=queue.poll();  
        System.out.println("%d ",tempNode.data);  
        if(tempNode.right!=null)  
        queue.add(tempNode.left.left);  
        if(tempNode.left!=null)  
        queue.add(tempNode.right.right);  
    }  
}
View Answer
Answer: a
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. 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)
View Answer

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

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

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

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

Answer: b
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. 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
View Answer

Answer: d
Explanation: In a binary search tree, a node’s left child is always lesser than the node and right child is greater than the node, hence an in-order traversal would print them in a non decreasing fashion.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.