Previously Asked GATE Questions on Trees

Question 1: Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always true? (GATE CS 2000) 
(a) LASTIN = LASTPOST 
(b) LASTIN = LASTPRE 
(c) LASTPRE = LASTPOST 
(d) None of the above 

Answer: (d) 

Explanation: It is given that the given tree is complete binary tree. For a complete binary tree, the last visited node will always be same for inorder and preorder traversal. None of the above is true even for a complete binary tree. 

The option (a) is incorrect because the last node visited in Inorder traversal is right child and last node visited in Postorder traversal is root. 

The option (c) is incorrect because the last node visited in Preorder traversal is right child and last node visited in Postorder traversal is root. 

For option (b), see the following counter example.

     1
   /    \
  2      3
 / \    /
4   5  6  

Inorder traversal is 4 2 5 1 6 3
Preorder traversal is 1 2 4 5 3 6 

Question 2: The most appropriate matching for the following pairs is (GATE CS 2000): :

X: depth first search 1: heap
Y: breadth-first search 2: queue
Z: sorting 3: stack

(a) X—1 Y—2 Z-3 
(b) X—3 Y—1 Z-2 
(c) X—3 Y—2 Z-1 
(d) X—2 Y—3 Z-1 

Answer: (c) 

Explanation: Stack is used for Depth first Search 
Queue is used for Breadth First Search 
Heap is used for sorting 

Question 3: Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree? 
(a) (1 2 (4 5 6 7)) 
(b) (1 (2 3 4) 5 6) 7) 
(c) (1 (2 3 4)(5 6 7)) 
(d) (1 (2 3 NULL) (4 5)) 

Answer: (c) 

Question 4: Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely (GATE CS 2004)?
i) preorder and postorder
ii) inorder and postorder
iii) preorder and inorder
iv) level order and postorder

a) (i) only
b) (ii), (iii)
c) (iii) only
d) (iv) only

Answer: (b)

Question 5: The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)? (GATE CS 2004)
a) 2
b) 3
c) 4
d) 6

Answer: (b)
Explanation: Constructed binary search tree will be..

10
/ \
1 15
\ / \
3 12 16
\
5

Question 6: A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set.

o Deletion of the smallest element
o Insertion of an element if it is not already present in the set

Which of the following data structures can be used for this purpose?
(a) A heap can be used but not a balanced binary search tree
(b) A balanced binary search tree can be used but not a heap
(c) Both balanced binary search tree and heap can be used
(d) Neither balanced binary search tree nor heap can be used

Answer: (b)

Explanation: A self-balancing balancing binary search tree containing n items allows the lookup, insertion, and removal of an item in O(log n) worst-case time. Since it’s a self-balancing BST, we can easily find out minimum element in O(logn) time which is always the leftmost element (See Find the node with the minimum value in a Binary Search Tree).

Since Heap is a balanced binary tree (or almost complete binary tree), insertion complexity for heap is O(logn). Also, complexity to get minimum in a min heap is O(logn) because removal of root node causes a call to heapify (after removing the first element from the array) to maintain the heap tree property. But a heap cannot be used for the above purpose as the question says – insert an element if it is not already present. For a heap, we cannot find out in O(logn) if an element is present or not. Thanks to the game for providing the correct solution.

Question 7: The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:
(a) 2^h -1
(b) 2^(h-1) – 1
(c) 2^(h+1) -1
(d) 2*(h+1)

Answer: (c)

Explanation: Maximum number of nodes will be there for a complete tree. Number of nodes in a complete tree of height h = 1 + 2 + 2^2 + 2*3 + …. 2^h = 2^(h+1) – 1

Question 8: The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:
(a) d e b f g c a
(b) e d b g f c a
(c) e d b f g c a
(d) d e f g b c a

Answer: (a)

Below is the given tree.

a

/ \

/ \

b c

/ \ / \

/ \ / \

d e f g

Question 9: A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n? 
(a) 3 
(b) 4 
(c) 5 
(d) 6

Answer: (c) 
For an n-ary tree where each node has n children or no children, following relation holds 

L = (n-1)*I + 1

Where L is the number of leaf nodes and I is the number of internal nodes.
Let us find out the value of n for the given data. 

L = 41 , I = 10
41 = 10*(n-1) + 1
(n-1) = 4
n = 5

Question 10: What is the number of binary search trees with 20 nodes with elements 1, 2, 3,…..20 such that the root of tree is 12 and the root of left subtree is 7? 
(a) 2634240 
(b) 1243561 
(c) 350016 
(d) 2642640 

Answer: (d) 

Explanation:
Number of nodes in left subtree = 11 {1, 2, 3, 4….11} 
Number of nodes in the right subtree = 8 {13, 14, ….20} 
Since for the left subtree root is 7 
Number of elements in the left part of left subtree = 6 {1, 2, 3..6} 
Number of elements in the right part of left subtree = 4 {8, 9, 10, 11} 
We know number of Binary Search trees with n nodes = (C(2n,n)/n+1) 
Number of BST with 6 nodes = (C(12,6)/7) = 132 
Number of BST with 4 nodes = (C(8,4)/5) = 14 
Number of BST with 8 nodes = (C(16,8)/9) =1430 
Total number of BST = 2642640 

Trees are foundational structures in computer science, serving as the backbone for numerous algorithms and data representations. GATE aspirants should be well versed in tree structures to prepare for the GATE Exam in 2024. This article aims to provide a concise yet comprehensive overview of trees, exploring key concepts crucial for a comprehensive understanding of the topic. To help candidates understand tree-based problem-solving scenarios, these notes provide invaluable insights and knowledge essential to success in GATE.