What is the time complexity of searching for an element in a balanced binary search tree (e.g., AVL or Red-Black)?

• A. O(1)
• B. O(log n)
• C. O(n)
• D. O(n log n)

Answer: (B)

In a balanced binary search tree, the time to search depends on the height of the tree because you move from the root down to a leaf, making one comparison per level. Each step is constant work, so the total time scales with how many levels you traverse. Balanced trees like AVL or Red-Black keep the height proportional to the logarithm of the number of nodes, specifically O(log n). That means you can locate any element by examining only about log n levels, which is why the search time is O(log n).

If the tree weren’t balanced, the height could grow to n, leading to O(n) search time. O(n log n) isn’t relevant to a single search—it would relate to operations that combine searching with other steps (like sort-related processes).