What is the time complexity of searching in a binary search tree?

The time complexity of searching for a value in a binary search tree (BST) depends on the shape of the tree. In the best-case scenario, where the tree is balanced, the time complexity is O(log n), where n is the number of nodes in the tree. This is because with each comparison, you effectively halve the number of nodes you need to consider, similar to how binary search works in a sorted array.

However, in the worst-case scenario, where the tree is completely unbalanced (e.g., takes the form of a linked list), the time complexity degrades to O(n). This situation occurs when each node has only one child, so you have to traverse through almost all the nodes to find the value you are looking for or to determine it does not exist.

To ensure the efficiency of search operations, it is vital to maintain the tree as balanced as possible, which is the principle behind self-balancing binary search trees like AVL trees and Red-Black trees. These trees offer guaranteed O(log n) search time complexity by automatically re-balancing themselves upon insertions and deletions.