GATE CSE 2021 Set 1 | Question: 10

Question

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)$

Comments

for picking element smaller than maximum can be done in constant time.

If the root has left node then answer is left node (in BST left is smaller than root so definitely it will be smaller than maximum)

Otherwise answer is root node (root node is smaller than right subtree).

So time complexity O(1)

Option D)

---

It’s Trivial.

Suppose we have a Skewed Binary tree.

Take two element compare them and we can conclude that O(1) …

Note: You can take any BST .. just compare a[root] and a[child of root]

Answer 1

If our data structure contains $n$ distinct elements then :

In all the standard data structures that we know/study about, If we want to pick/find an element that is not maximum (smaller than maximum) then time complexity will be $\Theta(1)$ because we only need to compare any two elements. Take any two elements that you can access in constant time, compare them, and return the smaller of those two elements.

PS: By “standard data structures that we know/study about” I mean the following :

Binary tree, Binary search tree, AVL tree, sorted or unsorted array, linked lists, arrays, stacks, queues, hash tables, heaps, etc.

NOTE: We don’t need to find the “Second Largest Number”. We need ANY number which is not the largest. So, take ANY two elements & the smaller in them is your answer. So, $O(1)$ time is required.

Comments

Why we are not consider the time which needed for searching maximum number??

---

Because we do not need to find the maximum element. “Not maximum element” means “Any element other than the maximum” will work. So, just find any two elements and find smaller between those two numbers.

---

Here the confusion is whether should we take the time complexity of finding the maximum element also into consideration?

In such doubts read the question again. In all gate pyqs the answer is always whatever is asked. 

Here it is :

 Time complexity of picking an element in T that is smaller than the maximum element in T

Here we just need to find the Time complexity of picking an element. That is the question simply. Now what to pick? → Any smaller element. Hence this is the entire question. The doubt of “whether to find the max element now vanishes 😊.” Thus it is $O(1)$ and not $O(n)$

Edit: It's not smallest but any smaller element Thanks @Deepak Poonia Sir.

---

@Abhrajyoti00

A typo: We don’t need to find the “smallest element”

---

If the question would have been tweaked like “For a BST where some elements are not distinct” then to find the smallest element such that it’s smaller than the maximum element would be O(log h + log h). Right ?

To find the minimum element (log h) time and to find max element (log h) time and then constant time to compare them.

For example:  

I am just curious to find the complexity. Please correct me if I am wrong.

 

BST with duplicate keys: https://stackoverflow.com/questions/300935/are-duplicate-keys-allowed-in-the-definition-of-binary-search-trees

---

@TusharRana The height of BST can be n-1 at worst case so finding maximum element will take O(n) time.

---

here to find the max element in the tree it will take O(logn) since it will only traverse the right subtree and to find the smaller than max element it will take o(1) therefore it will be o(logn)*1

is my understanding correct?

---

@Meghana Kelam, We don’t need to find the “Second Largest Number”. We need ANY number which is Not largest. So, take ANY two elements & the smaller in them is your answer. So, $O(1)$ time is required. 

Answer 2

ANS IS D.

HERE WE HAVE TO FIND THE ELEMENT  WHICH IS SMALLER THAN MAXIMUM ELEMENT. WHICH CAN BE FOUND IN CONSTANT TIME. 

Answer 3

D is the right answer .

For picking an element in BST that is smaller than the maximum element you need at most 1 comparision ,hence constant operation .