Binary Search Trees
Add one rule to a binary tree — everything left is smaller, everything right is larger — and search becomes logarithmic. It is the same halving as binary search, now on a structure that also supports cheap insertion.
- State the BST property as a representation invariant.
- Search, insert and delete while preserving it.
- Explain why an in-order traversal comes out sorted.
- Say when a BST degrades to $O(n)$ and why.
A sorted list gives $O(\log n)$ search but $O(n)$ insertion. A linked list reverses that. A BST offers $O(\log n)$ for both — when it stays balanced, which is the catch this unit is honest about.
Database indexes are tree structures of this family. Python's
dict uses hashing instead, which is faster for lookup but cannot
give you the keys in order — the thing a BST does for
free.
Binary search trees were described independently by several groups around 1960. The balancing problem was solved within two years by AVL trees, and later by red-black trees, which is what most standard libraries use today.
The property
A binary search tree is a binary tree where, for every node:
This must hold at every node, not just the top — which is the point people most often miss.
class BST:
"""A binary search tree.
Attributes:
_root: the value at this node, or None if empty
_left: the left subtree
_right: the right subtree
Representation invariants:
- if self._root is None then self._left is None and
self._right is None
- every value in self._left is < self._root
- every value in self._right is > self._root
"""
def __init__(self, root) -> None:
"""Initialize a BST containing root, or empty if root is None."""
self._root = root
if root is None:
self._left = None
self._right = None
else:
self._left = BST(None)
self._right = BST(None)
def is_empty(self) -> bool:
"""Return whether this tree is empty."""
return self._root is NoneEmpty subtrees are empty BSTs rather than None. That keeps
every recursive call uniform — no branch has to test whether a subtree
exists before recursing into it.
Checking only that each node's immediate children are on the right sides is not enough. A value deep in the left subtree that exceeds the root breaks the tree even if every parent-child pair looks fine. The invariant quantifies over every value in the subtree.
Search
def __contains__(self, item) -> bool:
"""Return whether item is in this BST.
>>> t = BST(5)
>>> t.insert(3)
>>> 3 in t
True
>>> 4 in t
False
"""
if self.is_empty():
return False
if item == self._root:
return True
if item < self._root:
return item in self._left # discard the entire right subtree
return item in self._right # discard the entire left subtreeTraverse left subtree, then root, then right subtree, and the values come out in increasing order.
def in_order(self) -> list:
"""Return the values of this BST in increasing order.
>>> t = BST(5)
>>> t.insert(3)
>>> t.insert(8)
>>> t.in_order()
[3, 5, 8]
"""
if self.is_empty():
return []
return self._left.in_order() + [self._root] + self._right.in_order()This falls straight out of the invariant: everything left is smaller, everything right is larger, so visiting in that order is sorted.
Insertion
def insert(self, item) -> None:
"""Insert item into this BST, keeping the BST property.
Does nothing if item is already present.
>>> t = BST(5)
>>> t.insert(3)
>>> 3 in t
True
"""
if self.is_empty():
self._root = item
self._left = BST(None)
self._right = BST(None)
elif item < self._root:
self._left.insert(item)
elif item > self._root:
self._right.insert(item)
# equal: already present, nothing to doDeletion
Deleting $5$ from a tree whose left subtree holds $3$ and $4$, right subtree $8$.
def _largest(self):
"""Return the largest value in this non-empty BST.
Preconditions: this tree is not empty.
"""
if self._right.is_empty():
return self._root
return self._right._largest()Keep going right until you cannot. The largest value is always the rightmost node, which is immediate from the invariant.
When it degrades
Insert $1, 2, 3, 4, 5$ in order into an empty BST. Each value is larger than everything before it, so each goes to the far right and the tree becomes a chain of five nodes — a linked list with extra steps.
Sorted input is the worst possible input, which is unfortunate because sorted input is common.
Self-balancing variants — AVL and red-black trees — restructure on insertion to keep the height logarithmic and give a genuine worst-case guarantee. Those come in later courses; knowing the plain BST does not guarantee it is what matters here.
• Checking the BST property only between a node and its immediate
children.
• Quoting $O(\log n)$ as though it were guaranteed.
• Getting the two-child deletion wrong by picking an arbitrary
replacement.
• Using None for empty subtrees and then needing a null check
in every method.
• Forgetting that in-order, not preorder, is the traversal that comes out
sorted.
Practice
Write out each answer before opening it. Original exercises written for this guide in the style of the course's weekly work.
State the BST invariant.
Answer
Insert $5, 3, 8, 1$ into an empty BST. Describe the shape.
Answer
Which traversal gives increasing order, and why?
Answer
What input makes a BST degrade to $O(n)$?
Answer
Write a method returning the smallest value.
Solution
def smallest(self):
"""Return the smallest value in this BST.
Preconditions: this tree is not empty.
"""
if self._left.is_empty():
return self._root
return self._left.smallest()_largest.What is the minimum possible height for $15$ values?
Answer
Why is checking each node against its children insufficient?
Answer
When would you prefer a BST to a Python dictionary?
Answer
Expanded topic checklist
Course coverage. This unit is part of the complete CSC148H1 topic map. It should cover the following items before you move on:
- The invariant. Stated over whole subtrees, not just children.
- Search and insert. Descending by comparison, and why both cost the height.
- Deletion. The three cases and the in-order predecessor trick.
- Complexity honestly. $O(\log n)$ balanced, $O(n)$ worst case, and what causes the worst case.
Binary search trees are the standard application of trees in this course. Check Quercus for the assigned exercises; BST insertion and deletion are common exam questions.
An ordering rule turns a tree into a search structure. Every comparison discards a subtree, so the cost is the height. Keeping the height small is a separate problem, and the plain BST does not solve it.
Deep practice extensions
Use these after the main practice set. They push on definitions and edge cases rather than routine calculation.
What determines the cost of a BST search?
Guide
Why the in-order predecessor when deleting a node with two children?
Guide
What causes the worst case?
Guide
What does a BST offer that a hash table does not?