What is the time complexity of searching for an element in a binary search tree (BST) in the average case?

Answer:

Explanation:

In a balanced binary search tree (BST), the average time complexity for searching an element is O(log n). This is because the height of the tree is proportional to log n, and searching involves traversing from the root to a leaf node, which takes log n steps.

In the worst case, if the BST becomes unbalanced (like a linked list), the time complexity degrades to O(n). However, for a well-balanced tree, the search complexity remains O(log n).

Using algorithms like AVL trees or Red-Black trees can help maintain balance in a BST and preserve the O(log n) search complexity.