1
GATE CSE 2020
+2
-0.67
In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a, b]? Assume that the number of reported elements is k.
A
$$\Theta \left( {\log n} \right)$$
B
$$\Theta \left( {\log n + k} \right)$$
C
$$\Theta \left( {k\log n} \right)$$
D
$$\Theta \left( {n\log k} \right)$$
2
GATE CSE 2020
Numerical
+2
-0.67
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.
3
GATE CSE 2019
Numerical
+2
-0.67
Let T be a full binary tree with 8 leaves. (A full binary tree has every level full). Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) _____.
4
GATE CSE 2016 Set 2
+2
-0.6
Consider the following $$New-order$$ strategy for traversing a binary tree:

$$\,\,\,\,\,\,\, \bullet \,\,\,\,\,$$ Visit the root;
$$\,\,\,\,\,\,\, \bullet \,\,\,\,\,$$ Visit the right subtree using $$New-order;$$
$$\,\,\,\,\,\,\, \bullet \,\,\,\,\,$$ Visit the left subtree using $$New-order;$$

The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ^ 6 7 * 1 + - is given by:

A
+ - 1 6 7 * 2 ^ 5 - 3 4 *
B
- + 1 * 6 7 ^ 2 - 5 * 3 4
C
- + 1 * 7 6 ^ 2 - 5 * 4 3
D
1 7 6 * + 2 5 4 3 * - ^ - New-order;
GATE CSE Subjects
EXAM MAP
Medical
NEET
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
CBSE
Class 12