What is the worst-case and average-case complexity of a binary search tree?

Binary Search Trees (BTS) have various levels of time complexity for their operations such as search, insert, and delete.

1. **Worst Case**: In the worst-case scenario, a binary search tree can become skewed in either direction (left or right- skewed). That means, each parent node has only one child node. This forms a linear structure similar to a linked list. In such a case, the operations on BST could take ‘O(n) time‘. Here ‘n‘ is the number of nodes, because we may have to traverse through all the nodes.

For example, if we have a tree like this:

50
 \
  70
   \
    80
     \
      90

Search, insertion or deletion will require to go through all the nodes, hence time complexity is ‘O(n)‘.

2. **Average Case**: The average-case time complexity in a balanced binary search tree is ‘O(log n)‘. In a balanced BST, the tree is very much ’balanced’, each left and right subtree contains an approximately equal number of nodes. As a result, the height of the tree remains small (logarithmic in relation to the number of nodes).

The operations of search, insert, delete operations can be performed in ‘O(log n)‘ time. This happens because you are essentially discarding half of the tree at each level (since you’re able to decide whether the target value would reside in the left or the right subtree).

For example, consider a balanced BST with 7 nodes:

      60
    /    \
  50      70
 /  \    /   \
40  55  65   80

If you want to search for the number 55, you can tell at each step which child node may contain this number, allowing discarding half part in each step, hence the time complexity is ‘O(log n)‘.

Please note that to maintain the average time complexity for a Binary search tree, it is crucial to keep the tree balanced, such as in an AVL tree or Red-Black tree.

To put it in terms of big thema, in the worst case, the complexity of a binary search tree operation is ‘O(n)‘. However, in an average case, this becomes ‘O(log n)‘.