Interview Cake
Costs
| Balanced | Unbalanced (Worst Case) | |
|---|---|---|
| space | ||
| insert | ||
| lookup | ||
| delete |
Quick reference
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.
Strengths:
-
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!).
Weaknesses:
- 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, an array or a hash map will be faster.
The Binary Search Tree Property
In a binary search tree, for each node:
- All nodes to the left are smaller than it
- All nodes to the right are larger than it.
Balanced Binary Search Trees
Two binary search trees can store the same values in different ways:
Image Edit: "Non Balanced" should be "Unbalanced".
Even though both of these trees satisfy the binary search tree property, a balanced binary search tree has better performance than an unbalanced one. (Read on to see why!)
Some trees (like AVL trees or Red-Black trees) rearrange nodes to ensure the tree always stays balanced.
Looking up an item
To find an item in a binary search tree, start from the root:
Compare the root node to the value we're looking for:
- If the value we're looking for is the root node, we're done!
- If the value we're looking for is smaller than the root node, then it must be to the left.
- If the value we're looking for is larger than the root node, then it must be to the right.
Repeat this process—comparing and then going left or right.
Until we find our value:
Lookups in unbalanced trees
Lookups involve walking from the top of the tree down to the leaves, so their time complexity is based on the height of the tree.
Balanced binary search trees are powerful because the number of levels in the tree grows very slowly even as more nodes are added. A balanced binary tree with n nodes has a height that's , making lookups in a balanced binary search tree .
In an unbalanced binary search tree, we might have very few nodes on each level of the tree. Look at this "worst case" scenario, where each node only has a right child:
Image Edit: Just the unbalanced tree.
To find 5 in that tree, we'll have to touch every other node.
More generally, this tree has n nodes and a height that's . That means lookups on unbalanced binary search trees are . Oof.
Inserting an item
Insert starts off just like lookup.
Beginning at the root node, work downward through the tree by comparing each node's value to the value we're inserting.
Eventually, we'll get to a spot where we need to go left or right but there's nothing there:
This is the place where the new node goes:
Just like lookup, insert takes for balanced binary search trees and for unbalanced binary search trees.
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!
