What is the average-case time complexity of searching for an element in a balanced Binary Search Tree?

Options

  • A. O(1)
  • B. O(log n)
  • C. O(n²)
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

B. O(log n)

Detailed Explanation

Searching in a reasonably balanced Binary Search Tree takes approximately O(log n) time because each comparison eliminates a substantial portion of the remaining search space. At every node, the search proceeds either to the left or right subtree. However, if a BST becomes highly unbalanced, it can resemble a linked list and searching can degrade to O(n). Therefore, tree height is an important factor in BST performance.
← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts