How to determine the time complexity of searching for a node in a binary tree?

The time complexity of searching for a node in a binary tree depends on its structure:

• In a regular binary tree (without ordering), the search may require traversing all nodes, so the worst-case complexity is — O(n), where n is the number of nodes.

• In a binary search tree (BST), if the tree is balanced, the search is performed in O(log n), since at each step we discard half of the tree.

• In the worst case, if the BST degenerates into a list (for example, all nodes go in one direction), the search complexity becomes O(n).

Example of searching in a balanced BST in Python:

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def search(root, key):
    if root is None or root.val == key:
        return root
    if key < root.val:
        return search(root.left, key)
    else:
        return search(root.right, key)

Here, the search operates in O(log n) for a balanced tree.