Provide an example of the worst-case search in binary trees.

The worst-case search in a binary search tree (BST) occurs when the tree is degenerate, essentially forming a linked list. This happens when elements are added in strictly increasing or decreasing order.

For example, if elements are added in the order 1, 2, 3, 4, 5:

    1
     \
      2
       \
        3
         \
          4
           \
            5

or in the order 5, 4, 3, 2, 1:

        5
       /
      4
     /
    3
   /
  2
 /
1

In such a tree, searching for any element becomes a sequential traversal, similar to searching in a linked list.

Worst-case search time: $O(n)$, where $n$ is the number of nodes in the tree. This is equivalent to linear search in an array or linked list.

Example of searching for element 5 in the first case:

1. Compare with root (1). 5 > 1, go right.
2. Compare with node 2. 5 > 2, go right.
3. Compare with node 3. 5 > 3, go right.
4. Compare with node 4. 5 > 4, go right.
5. Compare with node 5. Found.

Five comparisons for a tree of five nodes.

In contrast, in a balanced binary search tree (e.g., red-black tree or AVL tree), search takes $O(\log n)$ time in the worst case.