Western Governors University (WGU) ICSC2100 C949 Data Structures and Algorithms I Practice Exam

In a Binary Search Tree (BST), the searching complexity is O(log n) when the tree is balanced. This is because, in a balanced BST, each comparison allows the algorithm to eliminate half of the remaining nodes from consideration, leading to a logarithmic number of comparisons relative to the total number of nodes, n.

When searching for a value, the algorithm starts at the root and compares the value with the current node. Based on whether the value is less than or greater than the current node, the search continues down the left or right subtree, respectively. This process effectively halves the required search space at every step. As a result, the time complexity can often be understood as the height of the tree, which is log n for balanced trees.

However, it's important to note that if the BST is not balanced and degenerates into a linked list (such as when elements are inserted in a sorted manner), the search time complexity can revert to O(n). Nonetheless, under the usual assumption of a balanced or well-structured BST, a searching complexity of O(log n) is expected.