What is the worst-case time complexity for searching in a binary search tree (BST)?

The worst-case time complexity for searching in a binary search tree (BST) is O(h), where h represents the height of the tree. In an ideal scenario, a BST is balanced, which means the height h is logarithmic relative to the number of nodes, giving a time complexity of O(log n). However, in the worst-case scenarios, a BST can become unbalanced, resembling a linked list. For example, if elements are inserted in a sorted order, each node will only have a right child, leading to a height of n.

Consequently, the worst-case time complexity for searching for a value (where h could equal n in the worst case) is O(h). This captures the worst-case scenario where the tree degenerates into a linear structure. Understanding that the height can vary based on how the tree is constructed is essential in evaluating the efficiency of search operations within a binary search tree.