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

The average insertion complexity of a binary search tree is O(log n). This is because, in a balanced binary search tree, each insertion operation requires traversing from the root to a leaf node. At each level of the tree, the number of nodes being considered for insertion is roughly halved, which corresponds to a logarithmic time complexity.

For example, if the tree is balanced and contains n elements, the height of the tree is log n, meaning that, on average, the insertion process will require traversing approximately log n levels before finding the correct location for the new node. This logarithmic behavior is particularly evident in scenarios where the elements are inserted in a random order, resulting in a balanced tree.

In contrast, if the binary search tree becomes unbalanced—such as when elements are inserted in a sorted order—the average insertion complexity can degrade to O(n), which reflects a scenario where the tree resembles a linked list. Hence, the average insertion complexity is optimally O(log n) for a balanced binary search tree.