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$?
Take the root. If it is not the maximum, it qualifies. Otherwise it has no right child, so its left child (or any left-subtree element) is smaller. This takes constant time.
More Trees and Binary Search Trees questions
GATE 2020 CS Q15– The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which…
GATE 2020 CS Q16– What is the worst case time complexity of inserting n2 elements into an AVL-tree with n…
GATE 2020 CS Q51– In a balanced binary search tree with n elements, what is the worst case time complexity…
GATE 2018 CS Q30– The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of…
GATE 2015 CS (CS1) Q15– The height of a tree is the length of the longest root-to-leaf path in it. The maximum and…
GATE 2015 CS (CS1) Q17– Which of the following is/are correct inorder traversal sequence(s) of binary search…