Binary Search Trees
A binary search tree (BST) is a binary tree that keeps its values in order. It combines the best of two structures: like a sorted list, you can search it by halving the possibilities at each step, and like a linked structure, you can insert and delete without shifting other items.
In this lesson you will build a BST class with search, insert and delete, use it to answer "closest value" questions, learn how to check whether a tree really is a BST, and see why an unbalanced BST can become as slow as a linked list.
The BST property
A binary tree is a BST if, for every node:
- every value in its left subtree is smaller than the node's value, and
- every value in its right subtree is larger.
That rule must hold for whole subtrees, not just for the direct children. In this course we assume the values are distinct; a real BST must choose a side for duplicates or keep a count in each node.
Because of the rule, searching is like binary search: compare with the current node, then go left for smaller values or right for larger ones, ignoring the other subtree completely.
Search and insert
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, key):
if self.root is None:
self.root = Node(key)
return
node = self.root
while True:
if key < node.key:
if node.left is None:
node.left = Node(key)
return
node = node.left
elif key > node.key:
if node.right is None:
node.right = Node(key)
return
node = node.right
else:
return # already present: ignore
def contains(self, key):
node, steps = self.root, 0
while node:
steps += 1
if key == node.key:
return True, steps
node = node.left if key < node.key else node.right
return False, steps
def inorder(self):
def walk(node):
if node:
yield from walk(node.left)
yield node.key
yield from walk(node.right)
return list(walk(self.root))
def minimum(self):
node = self.root
while node.left:
node = node.left
return node.key
tree = BST()
for pin in [302001, 124001, 411001, 110001, 226001, 682001, 560001]:
tree.insert(pin)
print(tree.inorder())
print(tree.contains(226001), tree.contains(400001))
print("smallest:", tree.minimum())[110001, 124001, 226001, 302001, 411001, 560001, 682001] (True, 3) (False, 2) smallest: 110001
The inorder traversal comes out sorted, which is the defining feature of a BST (see Tree Traversals). The smallest key is found by always going left, the largest by always going right. Searching for a missing PIN code took only 2 steps: it followed one path down and fell off the bottom.
Insert and search both walk one path from the root, so they cost O(h), where h is the height of the tree. The code uses loops rather than recursion, so even a very tall tree cannot hit Python's recursion limit.
Balance decides the speed
O(h) is only good news if h is small. If keys arrive in random order, the tree is usually bushy, with height around 2 to 3 times log₂ n. If keys arrive already sorted, each new key is bigger than everything so far and goes to the far right: the tree becomes a chain and h = n - 1.
import random
from collections import deque
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"
child = getattr(node, side)
if child is None:
setattr(node, side, Node(key))
return root
node = child
def height(root): # level order, so no recursion limit
levels, queue = 0, deque([root])
while queue:
for _ in range(len(queue)):
node = queue.popleft()
for child in (node.left, node.right):
if child:
queue.append(child)
levels += 1
return levels - 1
random.seed(11)
n = 2000
shuffled = random.sample(range(n), n)
for name, keys in [("random order", shuffled), ("sorted order", range(n))]:
root = None
for k in keys:
root = insert(root, k)
print(f"{name}: height {height(root)}")random order: height 22 sorted order: height 1999
With random input, a search follows at most 23 nodes. With sorted input, it can follow 2,000, no better than a linked list. Real systems cannot hope for random input, so they use self-balancing BSTs, such as AVL trees and red-black trees. After each insert or delete, these trees perform small local rearrangements called rotations that keep the height O(log n) in every case.
Deleting a node
Deletion has three cases, depending on how many children the node has:
- No children (a leaf): just remove it.
- One child: replace the node with its only child.
- Two children: find the node's inorder successor (the smallest key in its right subtree), copy that key into the node, then delete the successor from the right subtree. The successor has no left child, so its own deletion is case 1 or 2.
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def delete(node, key):
if node is None:
return None # key not found
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: # cases 1 and 2
return node.right
if node.right is None:
return node.left
successor = node.right # case 3
while successor.left:
successor = successor.left
node.key = successor.key
node.right = delete(node.right, successor.key)
return node
def inorder(node):
return inorder(node.left) + [node.key] + inorder(node.right) if node else []
# 50
# / \
# 30 70
# / \ / \
# 20 40 60 80
root = Node(50, Node(30, Node(20), Node(40)), Node(70, Node(60), Node(80)))
root = delete(root, 20) # a leaf
root = delete(root, 30) # one child (40)
root = delete(root, 50) # two children: successor is 60
print(inorder(root), "new root:", root.key)[40, 60, 70, 80] new root: 60
The recursive delete() returns the (possibly new) root of each subtree, and the parent stores it back in node.left or node.right. That one pattern handles all three cases without tracking parents by hand. Each deletion follows one path down, so it is O(h).
Floor and ceiling queries
A BST can answer "the closest value not bigger than x", called the floor. Isha has ₹1,750 and wants the most expensive phone cover she can afford. Walk down the tree: when a key fits the budget, remember it and go right to look for something bigger that still fits; otherwise go left.
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def floor(node, budget):
best = None
while node:
if node.key == budget:
return node.key
if node.key < budget:
best = node.key # fits; try to find a bigger one
node = node.right
else:
node = node.left # too expensive
return best
prices = Node(1200, Node(600, Node(399), Node(899)),
Node(1999, Node(1499), Node(2499)))
for budget in [1750, 650, 3000, 300]:
print(budget, "->", floor(prices, budget))1750 -> 1499 650 -> 600 3000 -> 2499 300 -> None
The ceiling (smallest value not less than x) is the mirror image. Both run in O(h).
Checking that a tree is a BST
"Is this binary tree a valid BST?" is a common interview question with a common wrong answer: checking only that each node's left child is smaller and its right child is larger. The rule must hold for entire subtrees. Pass down the allowed range instead: everything in a left subtree must be below the parent's key, everything in a right subtree must be above it.
import math
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def children_only(node): # WRONG
if node is None:
return True
if node.left and node.left.key >= node.key:
return False
if node.right and node.right.key <= node.key:
return False
return children_only(node.left) and children_only(node.right)
def is_bst(node, low=-math.inf, high=math.inf): # RIGHT
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)
# 50
# / \
# 30 70
# \
# 60 <- 60 is bigger than 50 but sits in 50's left subtree
tricky = Node(50, Node(30, None, Node(60)), Node(70))
print("children only:", children_only(tricky))
print("with ranges: ", is_bst(tricky))children only: True with ranges: False
Another correct method is to do an inorder traversal and check that the values are strictly increasing.
Common mistakes
- Checking only direct children when validating a BST. Pass down a range.
- Forgetting to reattach the subtree after deletion (
node.left = delete(node.left, key)). - Assuming O(log n) for a plain BST. Sorted input makes it O(n); use a balanced tree.
- Not deciding about duplicates. Either reject them, send them consistently to one side, or keep a count.
Key points
- In a BST, every key in the left subtree is smaller and every key in the right subtree is larger.
- Search, insert, delete, minimum, maximum, floor and ceiling all walk one path: O(h).
- Inorder traversal of a BST gives the keys in sorted order.
- Delete has three cases; with two children, copy the inorder successor and delete it instead.
- Random inserts give a height near O(log n); sorted inserts give O(n). Balanced trees such as red-black trees guarantee O(log n).
- Java
TreeMap/TreeSetand C++std::map/std::setare balanced BSTs; Python usesdictorbisectinstead.
Exercise
Write count_in_range(node, low, high) that counts the keys between low and high (inclusive) in a BST, skipping any subtree that cannot contain such keys. Test it on the phone cover prices tree from the floor example with the ranges 500 to 1500 and 2000 to 5000.
Show solution
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def count_in_range(node, low, high):
if node is None:
return 0
if node.key < low: # whole left side is too small
return count_in_range(node.right, low, high)
if node.key > high: # whole right side is too big
return count_in_range(node.left, low, high)
return (1 + count_in_range(node.left, low, high)
+ count_in_range(node.right, low, high))
prices = Node(1200, Node(600, Node(399), Node(899)),
Node(1999, Node(1499), Node(2499)))
print(count_in_range(prices, 500, 1500))
print(count_in_range(prices, 2000, 5000))4 1
When a key is below the range, its whole left subtree is even smaller, so only the right subtree is searched (and the mirror case for keys above the range). This pruning is what makes BST range queries fast.
Quick Quiz
1. Which traversal of a BST gives the keys in sorted order?
Inorder visits left (smaller), node, right (larger).
2. What happens to a plain BST when keys are inserted in sorted order?
Each new key goes to the far right, so the tree degenerates into a linked list.
3. When deleting a node with two children, which key replaces it?
The successor is larger than everything on the left and smaller than everything else on the right.
4. Which of these is a balanced binary search tree?
TreeMap is a red-black tree; the other two are hash tables.
Learn DSA with a mentor
Free lessons get you started. Our Java, C & C++ Programming training adds real projects and code reviews from working developers.
- Project-based learning
- Mentor code reviews
- Free counselling call