1
GATE CSE 2015 Set 1
+1
-0.3
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
2
GATE CSE 2015 Set 1
+1
-0.3
What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
A
$$\Theta \left( {\log n} \right)$$ for both insertion and deletion
B
$$\Theta \left( n \right)$$ for both insertion and deletion
C
$$\Theta \left( n \right)$$ for insertion and $$\Theta \left( {\log n} \right)$$for deletion
D
$$\Theta \left( {\log n} \right)$$ for insertion and $$\Theta \left( n \right)$$ for deletion
3
GATE CSE 2015 Set 2
+1
-0.3
Consider a complete binary tree where the left and the right sub-trees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is
A
$$\Omega \left( {\log \,\,n} \right)$$
B
$$\Omega \left( n \right)$$
C
$$\Omega \left( {n\,\,\log \,\,n} \right)$$
D
$$\Omega \left( {{n^2}} \right)$$
4
GATE CSE 2015 Set 2
Numerical
+1
-0
A binary tree $$T$$ has $$20$$ leaves. The number of nodes in $$T$$ having two children is _______________.