Binary Search Tree

Question 1
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index _______.
A
510
B
999
C
509
D
501
GATE CSE 2022   Data Structure
Question 2
A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
A
\Theta(n\log n)
B
\Theta(n)
C
\Theta(\log n)
D
\Theta(1)
GATE CSE 2021 SET-1   Data Structure
Question 3
What is the in-order successor of 15 in the given binary search tree?

A
18
B
6
C
17
D
20
ISRO CSE 2020   Data Structure
Question 4
The preorder traversal of a binary search tree is 15,10,12,11,20,18,16,19. Which one of the following is the postorder traversal of the tree?
A
10,11,12,15,16,18,19,20
B
11,12,10,16,19,18,20,15
C
20,19,18,16,15,12,11,10
D
19,16,18,20,11,12,10,15
GATE CSE 2020   Data Structure
Question 5
The pre-order transversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:
A
2,6,7,8,9,10,12,15,16,17,19,20
B
2,7,6,10,9,8,15,17,20,19,16,12
C
7,2,6,8,9,10,20,17,19,15,16,12
D
7,6,2,10,9,8,15,16,17,20,19,12
GATE CSE 2017 SET-2   Data Structure
Question 6
Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are :
Note: The height of a tree with a single node is 0.
A
4 and 15 respectively
B
3 and 14 respectively
C
4 and 14 respectively
D
3 and 15 respectively
GATE CSE 2017 SET-1   Data Structure
Question 7
The number of ways in which the numbers 1,2,3,4,5,6,7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _____.
Note: The height of a tree with a single node is 0.
A
2
B
8
C
64
D
32
GATE CSE 2016 SET-2   Data Structure
Question 8
While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is
A
65
B
67
C
69
D
83
GATE CSE 2015 SET-3   Data Structure
Question 9
What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
A
\Theta (logn) for both insertion and deletion
B
\Theta (n) for both insertion and deletion
C
\Theta (n)for insertion and \Theta (logn) for deletion
D
\Theta (logn) for insertion and \Theta (n) for deletion
GATE CSE 2015 SET-1   Data Structure
Question 10
Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?
I. 3, 5, 7, 8, 15, 19, 25
II. 5, 8, 9, 12, 10, 15, 25
III. 2, 7, 10, 8, 14, 16, 20
IV. 4, 6, 7, 9 18, 20, 25
A
I and IV only
B
II and III only
C
II and IV only
D
II only
GATE CSE 2015 SET-1   Data Structure
There are 10 questions to complete.

Leave a Comment