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 \)?
Show Hint
- \( \Theta(n \log n) \)
- \( \Theta(n) \)
- \( \Theta(\log n) \)
- \( \Theta(1) \)
The Correct Option is D
Solution and Explanation
Step 1: Understanding the question.
The question asks for the time required to pick any element that is smaller than the maximum element in a binary search tree.
Step 2: Key observation.
In a BST with distinct elements, the maximum element is the rightmost node. Any other node in the tree automatically satisfies the condition of being smaller than the maximum.
Step 3: Time complexity.
We can simply pick the root (or any arbitrary node other than the maximum) without performing any traversal or comparison. This operation takes constant time.
Step 4: Conclusion.
Thus, the time complexity is \( \Theta(1) \).
Top Questions on Trees
- In a B+- tree where each node can hold at most four key values, a root to leaf path consists of the following nodes: \( A = (49, 77, 83, -) \)
\( B = (7, 19, 33, 44) \)
\( C = (20^*, 22^*, 25^*, 26^*) \)
The *-marked keys signify that these are data entries in a leaf. Assume that a pointer between keys \( k_1 \) and \( k_2 \) points to a subtree containing keys in \([ k_1, k_2 )\), and that when a leaf is created, the smallest key in it is copied up into its parent. A record with key value 23 is inserted into the B+- tree. The smallest key value in the parent of the leaf that contains 25* is ___________ . (Answer in integer) - Suppose the values 10, −4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let \( T \) be the resulting binary search tree. The number of edges in the path from the node containing 19 to the root node of \( T \) is \underline{{1cm}}. {(Answer in integer)}
- Consider the following algorithm tt{someAlgo that takes an undirected graph \( G \) as input.} tt{someAlgo(G)} Let \( v \) be any vertex in \( G \). Run BFS on \( G \) starting at \( v \). Let \( u \) be a vertex in \( G \) at maximum distance from \( v \) as given by the BFS. Run BFS on \( G \) again with \( u \) as the starting vertex. Let \( z \) be the vertex at maximum distance from \( u \) as given by the BFS. Output the distance between \( u \) and \( z \) in \( G \). The output of tt{someAlgo(T)} for the tree shown in the given figure is ___________ . (Answer in integer) \begin{center} \includegraphics{q59_fig.png} \end{center}
- Consider a binary tree \( T \) in which every node has either zero or two children. Let \( n%gt;0 \) be the number of nodes in \( T \). Which ONE of the following is the number of nodes in \( T \) that have exactly two children?
A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:
P: Unsorted doubly linked list with pointers to the head node and tail node of the list.
Q: Min-heap implemented using an array.
R: Binary Search Tree.
Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size \( n \) of these data structures?
Questions Asked in GATE CS exam
In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is ______________. {(Answer in integer)}
- GATE CS - 2025
- Flip-Flop
Consider the following C code segment:
int x = 126, y = 105; do { if (x > y) x = x - y; else y = y - x; } while (x != y); printf("%d", x);The output of the given C code segment is ____________. (Answer in integer)
- GATE CS - 2025
- Programming in C
The following two signed 2’s complement numbers (multiplicand \( M \) and multiplier \( Q \)) are being multiplied using Booth’s algorithm:
Multiplicand (\( M \)) Multiplier (\( Q \)) 1100 1101 1110 1101 1010 0100 1010 1010 The total number of addition and subtraction operations to be performed is __________. (Answer in integer)
- GATE CS - 2025
- Complementation
The maximum value of \(x\) such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is __________ (answer in integer).
- GATE CS - 2025
- Programming and Data Structures
Consider the following C program
The value printed by the given C program is __________ (Answer in integer).- GATE CS - 2025
- Programming in C