Binary Search Tree

A binary search tree are a special type of binary tree that are ordered so every node is as follows: node→left→value < node→value < node→right→value

Operation Complexity

If a binary tree is properly balanced, search, insertion and deletion are all

$$O(\log n)$$

However, there is an adverserial case where the binary search tree is effectively a linked list, a super-right heavy tree, where the worst case time complexity is then

$$O(n)$$

However, that case can only occur if the tree is not balanced.