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

The complexity of finding a node in a binary tree depends on its structure: whether it is balanced or not.

1. In a balanced binary search tree (BST):

Each comparison rules out half of the remaining elements. Average and best-case complexity: O(log n)

2. In an unbalanced tree:

If elements are inserted, for example, in increasing order, the tree turns into a chain (a list). Worst-case complexity: O(n)

3. Example:

To find 9: 8 → 10 → 9 - three steps (≈ log₂7 ≈ 3).

Summary:

• Average case (balanced tree): O(log n)
• Worst case (degenerate tree): O(n)