Table of contents
1.
Introduction
2.
Gate Questions on Tree Traversal
3.
Frequently Asked Questions
4.
Conclusion
Last Updated: Mar 27, 2024

Gate Questions on Tree Traversal: Part 1

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

The term "tree traversal" refers to the process of visiting each node in a tree. There is only one method to traverse a linear Data Structure like a stackqueue, or linked list. However, there are several ways to travel or visit each node in a tree. The three alternative modes of tree traversal are as follows:

  • Inorder tree traversal
  • Pre-order tree traversal
  • Postorder tree traversal

 

Let us understand each traversal briefly:

  1. Inorder tree traversal: A traversal approach that follows the policy, i.e., 'Left Root Right,' is an inorder tree traversal. 'Left Root Right' denotes that the root node's left subtree is read first, followed by the root node, and finally, the right subtree of the root node. The name inorder implies that the root node is located between the left and right subtrees.
     
  2. Pre-order tree traversal: A pre-order tree traversal is a traversal approach that follows the 'Root Left Right' policy. 'Root Left Right' indicates that the tree's root node is read first, followed by the left and right subtree. The name Pre-order demonstrates that the root node would be visited first in this case.
     
  3. Postorder tree traversal: A traversal strategy that follows the policy, i.e., 'Left Right Root,' is known as a postorder tree traversal. 'Left Right Root' indicates that the root node's left subtree is read first, followed by the right subtree and the root node. The term "Postorder" implies that the tree's root node will be examined last.

 

Refer to InorderPreorderPostorder, and Level Order tree traversals for better understanding and getting started with traversals and their approach. 

Let us now go through some of the crucial gate questions on tree traversal.

Gate Questions on Tree Traversal

Below are some commonly asked gate questions on tree traversal in the GATE examination.

1. Assume the digits 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are added in that sequence into a binary search tree that is initially empty. The binary search tree follows the standard natural number ordering. What is the resulting tree's inorder traversal sequence?
 

a) 7 5 1 0 3 2 4 6 8 9

b) 0 2 4 3 1 6 5 9 8 7

c) 9 8 6 4 2 3 0 1 5 7

d) 1 2 3 4 5 6 7 8 9

Ans. d) 0 1 2 3 4 5 6 7 8 9
Explanation: The digits 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are added in that order into a binary search tree that was previously empty, using the standard natural number ordering. The integers sorted in ascending order always yield the inorder sequence of such a binary search tree. As a result, option (D) is the correct answer.
 

2. Assume that +,-, x and are left-associative, and that ^ is right-associative. The precedence order is ^, ×, +, −. The postfix expression corresponding to the infix expression "a + b × c − d ^ e ^ f " is

a) abc x + de ^ f ^ −

b) ab + c × d − e^f^

c) abc x + def ^ ^ −

d) − + a × b c^^ def

Ans. c) abc x + def ^ ^ −
Explanation:The postfix conversion of the given expression is:

a + b × c − ( d ^( e ^ f))
a + b × c − ( d ^( e f ^ ))
a + b × c − ( d e f ^ ^)
(a + (b × c)) − d  e f ^ ^
(a + (b c x)) − d  e f ^ ^
(a (b c x) +) − d  e f ^ ^
(a b c x +) - (d e f ^ ^)
(a b c x +) - (d e f ^ ^)
a b c x + d e f ^ ^ -

Hence option (C) is the correct answer.
 

3. If the trees Tree-1 and Tree-2 are the ones listed below:

Which traversals of Tree-1 and Tree-2 will yield the same sequence, respectively?

a) Postorder, inorder

b) Postorder, preorder

c) Inorder, preorder

d) Preorder, postorder

e) None of the above

Ans. e)None of the above
Explanation:
Tree 1: 
PRE ORDER: A B D E G H I J F C 
IN ORDER: B G E H I J D F A C 
POST ORDER: G J I H E F D B C A 
Tree 2: 
PRE ORDER: G F E I J H C D B A 
IN ORDER: G J I H E F B D C A F
POST ORDER: J H I E B D A C F G
No order matches in both trees. Hence answer is (e).
 

4. FBGADCE was the outcome of traversing a tree in sequence. The tree's pre-order traversal would then result in

a) ABFGCDE

b) BFGCDEA

c) FGBDECA

d) AFGBDEC

Ans. a) ABFGCDE
Explanation: The tree's inorder traversal is as follows:
 As a result, the following tree's pre-order traversal is ABFGCDE. Option (a) is the correct answer.
 

5. Level order Traversal of a rooted tree starting from the root can be done by performing:

a) Depth First Search

b) Root Search

c) Deep Search

d) Breadth-First Search

Ans. d) Breadth-First Search
Explanation:  Level order Traversal of a rooted Tree can be done by starting from the root and performing Breadth-First Search. Hence option (d) is correct.
 

6. dbeafcg and abdecfg are the inorder and pre-order Traversals of a binary Tree, respectively. The postorder traversal is

a) debfagc

b) dbefcga

c) debfgca

d) dbefacg

Ans. c) debfgca
Explanation: We can identify post order by looking at pre-order (parent left right) and inorder (left parent right). It is evident from preorder(a(bdecfg)) that 'a' is the parent node (root node). We will now search for the left subtree via inorder traversal, i.e., dbe and fcg. We'll use the same procedure to discover the root node, left subtree, and right subtree of these subtrees. This will 
provide us with option (c) as the correct answer.

 

7. Consider the following statements: 

(A) A rooted tree can be traversed using a Depth-first search. 

(B) To list the vertices of an ordered rooted tree, pre-order, postorder, and inorder are performed. 

(C) Huffman's approach is utilized to find an optimal binary tree with specified weights. 

(D) Topological sorting assigns labels to parents greater than those assigned to their children. 

Which of the following statements is correct?

 

a) (A) and (B)

b) (C) and (D)

c) (A), (B) and (C)

d) (A), (B), (C) and (D)

Ans. d) (a), (b), (c) and (d)
Explanation: All of the given statements are true.
 

8. To enter a series of items 9,6,5,8,7,10 into an empty AVL tree, how many rotations are required?

a) 4

b) 3

c) 2

d) 0

Ans. b) 3
Explanation: The following diagram depicts the insertion and rotation of the various elements:
Hence a total number of 3 rotations are required. Option (b) is correct.
 

9. Select the corresponding prefix form of the formula (a + (b c))* ((d e)/(f + g h))

a) * +a − bc /− de − +fgh

b) * +a −bc − /de − +fgh

c) * +a − bc /− ed + −fgh

d) * +ab − c /− ed + −fgh

Ans.  a) * +a − bc /− de − +fgh
Explanation:  The prefix form of the expression may be written as:
= (a + (b − c))* ((d − e) / (f + g − h)) 
= (a + (- b c)) * ((- d e) / ( + f g - h))
= (+ a - b c) * ((- d e) / (- + f g h)
= (+ a - b c) * (/ - d e - + f g h)
= * + a - b c / - d e - + f g h
 

10. Assume the digits 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are entered in that sequence into a binary search tree that is originally empty. The binary search tree employs a natural number reversal order, with 9 presumed to be the smallest and 0 supposed to be the biggest. The produced binary search tree is traversed in sequence: 

a) 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

b) 9, 8, 6, 4, 2, 3, 0, 1, 5, 7

c) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

d) 0, 2, 4, 3, 1, 6, 5, 9, 8, 7

Ans. a) 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
Explanation: The keys are always produced in ascending order when traversing a binary search tree in-order. In this question, natural numbers are ordered in reverse order, with 9 being the smallest and 0 being the greatest. As a result, the sequence will be 9, 8, 7, 6, 5, 4, 3, 2, 1, 0. As a result, option (a) is the correct answer.
 

11. Consider G to be a straightforward undirected graph. Let TD represent a G depth-first search tree. Let TB represent a G's breadth-first search tree. Consider the statements below. (I) About TD, no edge of G is a cross edge. (In G, a cross edge is a connection between two nodes in which neither is an ancestor of the other in TD.) (II) If u is at depth i and v is at depth j in TB for every edge (u, v) of G, then |i- j| = 1. Which of the following assertions must be true?

a) I only

b) II only

c) Both I and II

d) Neither I nor II

Ans. a) I only
Explanation: Tree, forward, back, and cross edges are the four types of edges that may be produced in DFS. Forward and back edges are the same thing in an undirected connected graph. In a graph, a cross edge connects one vertex v to another vertex u, where u is neither an ancestor nor a descendant of v. As a result, a cross edge is not feasible in an undirected graph. As a result, assertion (I) is true. Take a counterexample of a complete graph with three vertices, such as K3 with XYZ, where X is the source, and Y and Z are on the same level, for the assertion (II). In BFS, there is also an edge connecting vertices Y and Z, i.e. |i-j| = 0 != 1. As a result, the assertion was proven to be untrue. Option (a) is the correct answer.
 

For more GATE questions on tree traversals, refer to our Gate Questions on Tree Traversal: Part 2 and Gate Questions on Tree Traversal: Part 3.

Check out this problem - Diameter Of Binary Tree

Frequently Asked Questions

  1. What is the best approach for traversing a tree?
    Typically, the best optimal algorithm is the one that is tailored to a particular use case and platform.
    It makes no difference whether we order in inorder, preorder, or postorder. Or whether we're a DFS or BFS player.
     
  2. What do you mean by an AVL tree?
    The AVL tree is a self-balancing Binary Search Tree (BST) with a maximum height difference between left and right subtrees of one for all nodes.
     
  3. What are trees used for?
    Data with an inherent hierarchical structure can be stored in trees. In its file management system, an operating system may, for example, utilize a tree for directories, files, and folders. They are dynamic, which means that adding and removing nodes is simple.
     
  4. Can we implement Trees with the Standard Template Library?
    The STL tree data structure does not exist since it lacks a "sequence" interface.

Conclusion

In this article, we have extensively discussed the crucial questions from the tree traversals and some previously asked questions in the gate exam.

Recommended problems -

 

We hope this blog has helped you enhance your knowledge regarding various gate questions on tree traversal. If you would like to learn more about tree traversals, gate syllabus, or questions on stacksqueues, etc., check out our articles on  Coding Ninjas Studio. Do upvote our blog to help other ninjas grow. Happy Coding!

Live masterclass