Data Structures · Lesson 10 of 16
Binary Search Trees
Go beyond insert and search in binary search trees: deletion, min and max, successor, floor and range queries, validation and why BSTs degrade.
- Intermediate
- 18 min read
- 4 objectives
Before this lessonLesson 9: Trees
What you will learn
- Delete nodes in all three cases
- Answer min, max, floor and successor queries
- Validate a BST with bounds
- Explain why height decides performance
Your Progress
0 of 16 lessons 0%
- Lessons0 / 16
- Completed0
- Est. time left~ 4 hours
Create a free account to keep your progress on every device.
Tip: pressing Next marks this lesson complete automatically.
In the Trees lesson you met the binary search tree (BST): every key in a node's left subtree is smaller, and every key in its right subtree is larger. You saw insert, contains and in-order traversal. This lesson finishes the job with the operations that make a BST genuinely useful: deleting, finding neighbours of a key, range queries, and checking that a tree is valid.
Why bother, when a hash table finds keys in O(1)? Because a hash table knows nothing about order. "What is the next appointment after 14:00?" or "list all orders between 100 and 200" are natural BST questions and slow hash table questions.
A small BST to work with
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root # duplicates are ignored
def inorder(root):
return inorder(root.left) + [root.key] + inorder(root.right) if root else []
root = None
for k in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, k)
print(inorder(root))[20, 30, 35, 40, 50, 60, 70, 80]
The tree looks like this: 50 at the root, 30 and 70 below it, then 20, 40, 60, 80, and 35 as the left child of 40. We will reuse the same code in the examples below.
Minimum and maximum
The smallest key is found by walking left until you cannot; the largest by walking right. Both cost O(h), where h is the height of the tree.
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None: return Node(key)
if key < root.key: root.left = insert(root.left, key)
elif key > root.key: root.right = insert(root.right, key)
return root
root = None
for k in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, k)
def minimum(node):
while node.left:
node = node.left
return node.key
def maximum(node):
while node.right:
node = node.right
return node.key
print(minimum(root), maximum(root))20 80
Floor, ceiling and successor
The floor of x is the largest key less than or equal to x. Walk down from the root: if the node's key is too big, go left; if it fits, remember it as a candidate and go right to look for something closer. The ceiling is the mirror image. The successor of a key is the smallest key strictly greater than it, which is what "next appointment" needs.
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None: return Node(key)
if key < root.key: root.left = insert(root.left, key)
elif key > root.key: root.right = insert(root.right, key)
return root
root = None
for k in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, k)
def floor(node, x):
best = None
while node:
if node.key == x:
return x
if node.key > x:
node = node.left
else:
best = node.key
node = node.right
return best
def successor(node, x):
best = None
while node:
if node.key > x:
best = node.key
node = node.left
else:
node = node.right
return best
print(floor(root, 45), floor(root, 10))
print(successor(root, 40), successor(root, 80))40 None 50 None
Range queries
To list every key between lo and hi, do an in-order walk but skip subtrees that cannot contain answers. If the node's key is below lo, its whole left subtree is too small. The cost is O(h + k), where k is the number of results.
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None: return Node(key)
if key < root.key: root.left = insert(root.left, key)
elif key > root.key: root.right = insert(root.right, key)
return root
root = None
for k in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, k)
def keys_between(node, lo, hi, out):
if node is None:
return out
if node.key > lo:
keys_between(node.left, lo, hi, out)
if lo <= node.key <= hi:
out.append(node.key)
if node.key < hi:
keys_between(node.right, lo, hi, out)
return out
print(keys_between(root, 33, 65, []))[35, 40, 50, 60]
Deletion: three cases
Deleting is the trickiest BST operation because the ordering rule must still hold afterwards. Find the node, then:
- No children (a leaf): just remove it.
- One child: replace the node with that child.
- Two children: copy in the in-order successor (the minimum of the right subtree), then delete that successor from the right subtree. The successor has no left child, so its own deletion is one of the easy cases.
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None: return Node(key)
if key < root.key: root.left = insert(root.left, key)
elif key > root.key: root.right = insert(root.right, key)
return root
def inorder(r):
return inorder(r.left) + [r.key] + inorder(r.right) if r else []
root = None
for k in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, k)
def delete(node, key):
if node is None:
return None
if key < node.key:
node.left = delete(node.left, key)
elif key > node.key:
node.right = delete(node.right, key)
else:
if node.left is None:
return node.right
if node.right is None:
return node.left
succ = node.right
while succ.left:
succ = succ.left
node.key = succ.key
node.right = delete(node.right, succ.key)
return node
root = delete(root, 20) # leaf
root = delete(root, 40) # one child (35)
root = delete(root, 50) # two children: root becomes 60
print(inorder(root), "root:", root.key)[30, 35, 60, 70, 80] root: 60
Validating a BST
A tempting check is "each node is greater than its left child and smaller than its right child". That is wrong: a grandchild can break the rule while every parent-child pair looks fine. Instead, pass down the allowed range (low, high) for each subtree.
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def is_bst(node, low=float("-inf"), high=float("inf")):
if node is None:
return True
if not (low < node.key < high):
return False
return is_bst(node.left, low, node.key) and is_bst(node.right, node.key, high)
good = Node(50, Node(30, Node(20), Node(40)), Node(70))
bad = Node(50, Node(30, Node(20), Node(60)), Node(70)) # 60 is left of 50
print(is_bst(good), is_bst(bad))True False
Height is everything
Every operation above costs O(h). If keys arrive in random order, h stays around 2 log n on average. But if keys arrive already sorted, each new key goes to the right of the last one and the tree becomes a linked list with h = n.
import random
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None: return Node(key)
node = root
while True:
side = "left" if key < node.key else "right"
nxt = getattr(node, side)
if nxt is None:
setattr(node, side, Node(key))
return root
node = nxt
def height(n):
return 1 + max(height(n.left), height(n.right)) if n else 0
keys = list(range(500))
sorted_root = None
for k in keys:
sorted_root = insert(sorted_root, k)
random.seed(7)
random.shuffle(keys)
random_root = None
for k in keys:
random_root = insert(random_root, k)
print("sorted inserts height:", height(sorted_root))
print("random inserts height under 30:", height(random_root) < 30)sorted inserts height: 500 random inserts height under 30: True
Real data is often sorted (timestamps, auto-increment IDs), so a plain BST is risky in production. The fix is a self-balancing tree, the topic of the next lesson.
Complexity
Operation Balanced (h = log n) Degenerate (h = n)
search / insert O(log n) O(n)
delete O(log n) O(n)
min / max O(log n) O(n)
floor / successor O(log n) O(n)
range query, k results O(log n + k) O(n)
in-order traversal O(n) O(n)
space O(n) O(n)Recap
- A BST keeps keys ordered, so it answers min, max, floor, successor and range queries that hash tables cannot.
- Every operation walks one root-to-leaf path, costing O(h).
- Delete has three cases; the two-child case swaps in the in-order successor.
- Validate with a (low, high) range, not by comparing parent and child only.
- Sorted inserts create a height-n chain, which is why balanced trees exist.
# Write your solution here
Finished reading? Mark this lesson complete to track your progress.