|Balanced||Unbalanced (Worst Case)|
A binary search tree is a binary tree where the nodes are ordered in a specific way. For every node:
- The nodes to the left are smaller than the current node.
- The nodes to the right are larger than the current node.
Checking if a binary tree is a binary search tree is a favorite question from interviews.
Good performance across the board. Assuming they're balanced, binary search trees are good at lots of operations, even if they're not constant time for anything.
- BSTs are sorted. Taking a binary search tree and pulling out all of the elements in sorted order can be done in using an in-order traversal. Finding the element closest to a value can be done in (again, if the BST is balanced!).
Balanced Binary Search Trees
Two binary search trees can store the same values in different ways:
Some trees (like AVL trees or Red-Black trees) rearrange nodes as they're inserted to ensure the tree is always balanced. With these, the worst case complexity for searching, inserting, or deleting is always , not .