What is the worst-case time complexity of searching in a highly skewed Binary Search Tree containing n nodes?

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)

C. O(n)

Detailed Explanation

A highly skewed BST can have a structure similar to a linked list, where each node has only one child. In this situation, searching may require visiting every node, resulting in a worst-case complexity of O(n). A balanced BST has height approximately O(log n), but an unbalanced BST can have height O(n). Self-balancing trees such as AVL trees and Red-Black trees are designed to prevent excessive skew and maintain efficient operations.
← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts