What is the time complexity for searching an element in a binary search tree…

In a Binary Search Tree (BST), searching typically takes O(log n) time on average because the tree is balanced, allowing us to eliminate half of the remaining nodes at each step. However, in the worst-case scenario, the BST becomes skewed or degenerate, resembling a linked list. This occurs when elements are inserted in sorted order (either ascending or descending), causing each node to have only one child. In this degenerate case, the height of the tree becomes equal to n (the number of nodes). Consequently, an algorithm may need to traverse from the root down to a leaf node, visiting every single element in the sequence. Therefore, the time complexity degrades from O(log n) to O(n). Option A is incorrect because constant time search is impossible without direct indexing. Option B represents the average or best-case complexity for a balanced tree, not the worst case.