|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.
- Compared to a sorted array, lookups take the same amount of time (), but inserts and deletes are faster ( for BSTs, for arrays).
- Compared to dictionaries, BSTs have better worst case performance— instead of . But, on average dictionaries perform better than BSTs (meaning time complexity).
- 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!).
- Poor performance if unbalanced. Some types of binary search trees balance automatically, but not all. If a BST is not balanced, then operations become .
- No operations. BSTs aren't the fastest for anything. On average, a list or a dictionary will be faster.
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 .
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!