UTpaper

Free mock tests & test series

Question 27

A binary search tree with N integers may have height ______ in the best case, and ______ in the worst case.

  1. AO(N), O(N)
  2. BO(N²), N
  3. CO(log₂N), O(N²)
  4. DO(log₂N), N−1
Show answerHide answer

Correct answer: (D) O(log₂N), N−1

Explanation

A balanced BST has height O(log₂N). If keys are inserted in sorted order the tree becomes a chain with height N−1.

From DSSSB TGT Computer Science Practice Set 4

This is question 27 of DSSSB TGT Computer Science Practice Set 4. See all questions of this paper with answers, or attempt the paper as a timed online test to get your score and all-India rank.