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 stack, queue, 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
- Preorder tree traversal
- Postorder tree traversal
Let us understand each traversal briefly:
-
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.
-
Preorder tree traversal: A preorder 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.
- 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 Inorder, Preorder, Postorder, and Level Order tree traversals for better understanding and getting started with traversals and their approach.
Let us go through some of the crucial gate questions on tree traversal.
Questions
Below are some commonly asked gate questions on tree traversal in the GATE examination.
1. If all of an undirected graph's edge weights are positive, then any subset of edges that links all of the vertices and has the least total weight is a ___.
a) grid
b) hypercube
c) tree
d) hamiltonian cycle
Ans. c) tree
Explanation: We want a subset of edges that connect all vertices and have the least overall weight. Therefore we'll call it the Minimum Spanning Tree. Option A - is irrelevant to the topic at hand. Option B - includes a cycle. Thus, all edges may or may not be connected. Option D - incorporates cycle. Therefore all edges may or may not be connected.
2. Nodes with the key values 10, 20, 40, 50, 70, 80, and 90 are explored in a binary search tree, though not necessarily in the specified sequence. How many alternative orders are available for these key values on the search path from the root to the node with the value 60?
a) 64
b) 128
c) 5040
d) 35
Ans. d)35
Explanation: There are two types of values: those that are less than 60 and those larger than 60. Smaller numbers, such as 10, 20, 40, and 50, are visited in that sequence. In the same way, 90, 80, and 70 are visited in that sequence.
Alternative orders available for these key values = No. of possible permutations of 7 numbers / (No. of possible permutations of numbers smaller than 60 * No. of possible permutations of numbers larger than 60)
= 7!/(4!3!)
= 35
3. If 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12 is the postorder traversals of a binary search tree. Then this tree's preorder traversal is:
a) 2, 6, 7, 8, 10, 9, 12, 15, 16, 17, 19, 20
b) 7, 6, 2, 9, 10, 8, 15, 16, 17, 20, 19, 12
c) 7, 2, 6, 8, 10, 9, 20, 17, 19, 15, 16, 12
d) 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20
Ans. d) 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20
Explanation: Because the provided tree is a binary tree, the inorder traversal will always be in sorted order, i.e., 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20, and so on. We can now draw that binary search tree with the specified postorder and inorder traversal. The final tree will be as follows:
As a result, the following will be the preorder traversal: 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Option (D) is the correct answer.
4. Which of the statements given below is incorrect in terms of depth-first search?
a) E edges are identified as tree edges in a depth-first traversal of a graph G with V vertices. G has a total number of connected components (E - V).
b) If implemented with an adjacency matrix, the depth-first search takes O(V2) time.
c) The depth-first search takes O(V + E) time using adjacency lists.
d) None of the above
Ans. a) E edges are identified as tree edges in a depth-first traversal of a graph G with V vertices. G has a total number of connected components (E - V).
Explanation: E edges are identified as tree edges in a depth-first traversal of a graph G with V vertices. G has a total number of linked components (V - E). The only option seems to be incorrect.
5. Which of the following sequences represents the provided tree's postorder traversal sequence?
a) f e g c d b a
b) g c b d a f e
c) f e d g c b a
d) g c d b f e a
Ans. d) g c d b f e a
Explanation: The postorder tree traversal strategy follows the policy 'Left Right Root.'
6. Every node in a complete n-ary tree has either 0 or n children. If x denotes the number of internal nodes, then the number of leaves in a complete n-ary tree is given by
a) x(n-1)+1
b) xn-1
c) xn+1
d) x(n+1)
Ans. a) x(n-1)+1
Explanation:
Since each internal node provides a total of n edges,
No of edges = n* (internal nodes,i.e.., x) - - (1)
Number of nodes = internal nodes + leaf nodes,
n = x + l
Now we know there are total n-1 edges in a tree with n nodes, so
no of edges = x+l-1 - - (2)
Combining (1) and (2)
n*x=x+l-1
x*(n-1)+1=l
7. Which of the statements below is false?
a) (n-1) edges exist in a tree with n nodes.
b) The postorder and preorder traversal results may create a labeled rooted binary tree uniquely.
c) There are (n+1) leaves in a complete binary tree with n internal nodes.
d) In a binary tree of height h, the maximum number of nodes is/are (2(h+1) -1).
Ans. a) and d)
Explanation: Option (a) and option (d) are valid. Option (b), on the other hand, is incorrect since "a labeled rooted binary tree cannot be uniquely created given its postorder and preorder traversal results." A uniquely formed binary tree requires inorder, preorder, and postorder. Option (c) is also untrue.
8. Consider the undirected graph below, which has the following node sequence.
i. a b e f d g c
ii. a b e f c g d
iii. a d g e b c f
iv. a d b c g e f
At node a, a Depth First Search (DFS) is initiated. The nodes are given in the order in which they were visited for the first time. Which of the above mentioned is (are) a feasible output?
a) ii and iii only
b) i and iii only
c) ii, iii, and iv only
d) i, ii, and iii
Ans. a) ii and iii only
Explanation:
i: abef->c or g has to be covered.
ii: abefcgd correct
iii: adgebcf correct
iv: adbc->e or f has to be addressed.
9. BCAD and ABCD are the inorder and preorder traversals of which of the following binary trees, respectively?
a) D
b) C
c) B
d) A
Ans. a) D
Explanation: The first element in Preorder is the root, and everything to the left of it in the inorder is in LST, while everything to the right is in RST.
So, in LST, A is the root of BC, while in RST, D is the root of BC. Options A and C are no longer acceptable.
Because B is first in preorder in BC, it should be the root. Option B has been eliminated.
So D is the correct answer.
10. In a binary search tree, the numbers 1, 2,.... n are entered in some sequence. The root's right subtree has p nodes in the resultant tree. The initial number entered in the tree is:
a) p
b) p + 1
c) n - p
d) n - p + 1
Ans. c) n - p
Explanation: The Binary Search Tree data structure is a node-based binary tree with the following properties:
- Only nodes with keys smaller than the node's key are found in the node's left subtree.
- Only nodes with keys larger than the node's key are located in the node's right subtree.
- Each subtree on the right and left must be a binary search tree. There must be no identical nodes.
Let's suppose n=12 and p=5. The root must be 12-5=7 (considering all unique elements in BST), and the root is the first element to be inserted in a BST.
As a result, the solution is (n-p).
11. Level order traversal of a rooted tree can be done by starting from the root and performing
a) preorder traversal
b) depth first search
c) breadth first search
d) inorder traversal
Ans. c) breadth first search
Explanation:
- Preorder traversal: Root, Left, Right
- Inorder traversal: Left, Root, Right
- Postorder traversal: Left, Right, Root
- Level order traversal: It starts at the root and calls BFS.
Level order traversal of a tree is breadth first traversal for the tree. For understanding the solution better, go through the level order traversal of a binary tree.
For more GATE questions on tree traversals, refer to our Gate Questions on Tree Traversal: Part 1 and Gate Questions on Tree Traversal: Part 3.