Data Structure Questions and Answers – Inorder Traversal

Uncategorized

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

data-structure-questions-answers-inorder-traversal-q1



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) 
{  
    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);  
    }  
}


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

You begin by traversing from the root, then to the left node, then to the left node again until you reach a leaf node. At that point, you print the node’s value or mark it as visited, and switch to the right subtree. Using the same algorithm until all of the binary tree’s nodes have been visited. Since it returns values from the underlying set in order, according to the comparator that set up the binary search tree, in-order traversal is widely used in binary search trees (hence the name). When deleting or freeing nodes and values in post-order traversal, an entire binary tree can be deleted or freed.

Leave a Reply

Your email address will not be published. Required fields are marked *