In a binary search tree, the average search time is generally _______ for a reasonably balanced tree.

Options

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

Correct Answer (Detailed Explanation is Below)

B. O(log N)

Detailed Explanation

For a reasonably balanced Binary Search Tree (BST), search generally takes O(log N) average time because each comparison moves the search toward one subtree. However, if a BST becomes highly skewed, its height can approach N, making the worst-case search complexity O(N). Balanced trees such as AVL trees and Red-Black trees maintain logarithmic height and therefore provide predictable search performance.

← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts