Exams › GATE › Technical

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?

1. Θ(n log n)
2. Θ(n)
3. Θ(log n)
4. Θ(1)

Correct answer: Θ(log n)

Solution

To pick an element smaller than the maximum, one can traverse to the rightmost node and then choose its parent or another suitable node. In a balanced BST, this takes proportional to the height of the tree, which is Θ(log n).

Related GATE Technical questions

• An array \([82, 101, 90, 11, 111, 75, 33, 131, 44, 93]\) is heapified. Which one of the following options represents the first three elements in the heapified array?
• Consider a binary min-heap containing 105 distinct elements. Let \(k\) be the index in the underlying array of the maximum element stored in the heap. The number of possible values of \(k\) is
• Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?
• The height of a binary tree is the maximum number of edges in any root-to-leaf path. The maximum number of nodes in a binary tree of height $h$ is:
• The maximum number of binary trees that can be formed with three unlabeled nodes is:
• The inorder and preorder traversals of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is

⚔️ Practice GATE Technical free + battle 1v1 →