Smaller on the left, larger on the right — one rule that turns search into a series of halvings. Then insert sorted data and watch the whole structure collapse into a linked list.
Controls
Traversal
The Tree
step 0
Insight
The BST rule, applied at every node: everything in the left subtree is smaller, everything in the right subtree is larger.
nodes0
height0
ideal height0
last search steps–
Complexity
Search (balanced)O(log n)
Search (degenerate)O(n)
SpaceO(n)
Binary Search Trees
Binary search made into a structure — and what happens when it loses its shape.
The problem it solves
A binary search tree keeps its values in sorted order by position. At every node: the entire left subtree is smaller, the entire right subtree is larger. Searching then works exactly like binary search — compare, discard half, repeat.
Search, Insert, Delete
Searching is a walk: compare with the current node, go left if smaller, right if larger, stop when equal or when you fall off the tree. Insertion follows the same walk and attaches the new node where the search failed.
Deletion is the fiddly one, with three cases:
Leaf — just remove it.
One child — the child takes its place.
Two children — replace the value with its in-order successor (the smallest value in the right subtree), then delete that successor. Only this choice preserves the BST rule.
In-Order Traversal Sorts For Free
Visit left subtree, then the node, then the right subtree. Because of the BST rule, this emits every value in ascending sorted order — press In and read the output.
The other two orders have their own uses: pre-order (node first) is how you copy or serialise a tree, and post-order (node last) is how you delete one safely, since children are freed before their parent.
The Fatal Weakness
Press Sorted input. Inserting already-sorted values means every new value is larger than everything before it, so it always goes right. The tree becomes a single downward chain — a linked list wearing a tree costume.
Height goes from O(log n) to O(n), and every operation degrades with it. This is not a rare edge case: inserting sorted data is extremely common in practice.
Which Is Why Self-Balancing Trees Exist
AVL trees and red-black trees detect when a subtree grows lopsided and perform rotations to restore balance, guaranteeing O(log n) regardless of insertion order. Red-black trees are what back std::map in C++ and TreeMap in Java.
Compare the height readout after pressing Balanced versus Sorted input with the same values — the gap is exactly what balancing buys.
BST or Hash Table?
A hash table is faster for pure lookup — O(1) versus O(log n). But a BST keeps its data ordered, which a hash table cannot. Use a tree when you need sorted iteration, range queries ("all values between 20 and 50"), or nearest-neighbour lookups. Use a hash table when you only ever ask "is this exact key present?".
Ordered structure, not just storage
A binary search tree keeps one invariant at every node:
Everything in the left subtree is smaller; everything in the right subtree is larger.
That single rule makes search work like binary search: compare, then discard half the tree.
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Searching for 6: 6 < 8 so go left; 6 > 3 so go right; found. Three comparisons for seven nodes.
Operation
Balanced
Degenerate
Search
O(log n)
O(n)
Insert
O(log n)
O(n)
Delete
O(log n)
O(n)
In-order traversal
O(n)
O(n)
Minimum / maximum
O(log n)
O(n)
The difference between those columns is the whole subject, and it is what balanced trees exist to guarantee.
Why an in-order traversal is sorted
Visit the left subtree, then the node, then the right subtree, and values come out in ascending order — because everything left is smaller and everything right is larger, recursively.
def inorder(node, out):
if node:
inorder(node.left, out)
out.append(node.value)
inorder(node.right, out)
That is the property hash tables cannot offer, and it is why BSTs are used where ordering matters:
Range queries — all values between 10 and 50, found by traversing a subtree.
Nearest neighbour — the closest value to a target.
Sorted iteration without sorting.
Successor and predecessor of a given value.
Minimum and maximum — walk left or right to the end.
A hash table does none of those. That is the trade: O(1) unordered lookup, or O(log n) with order.
The degenerate case
Insert 1, 2, 3, 4, 5 into an empty BST in that order and every node becomes the right child of the last. The tree is a linked list, and every operation is O(n).
Sorted input produces the worst possible tree. That is not a rare pathological case — inserting records in id order, or in date order, is entirely normal.
Three responses:
Self-balancing trees. AVL and red-black trees rotate on insertion to keep the height O(log n) automatically. This is what production implementations use.
Randomised insertion order, if you control it. Expected height O(log n).
A different structure. A sorted array with binary search, or a skip list, or a B-tree for disk-based data.
Tree
Balance rule
Character
AVL
Heights differ by at most 1
Strictly balanced; faster lookups
Red-black
Colour rules bound the height
Fewer rotations; faster insertion
B-tree
Many keys per node
Designed for disk pages
Treap
Random priorities
Simple, probabilistic balance
Red-black trees are what most standard libraries use for ordered maps — C++'s std::map, Java's TreeMap — because they balance insertion and lookup cost well.
The fatal weakness, measured
A BST gives O(log n) search when it is balanced and O(n) when it is not, and nothing in the plain insert algorithm prevents the second. The gap between those two is the whole reason self-balancing trees exist, and it opens up on the most ordinary input there is.
example_01.pyPython
class BST:
def __init__(self):
self.root = None
self.comparisons = 0
def insert(self, v):
if self.root is None:
self.root = [v, None, None]
return
node = self.root
while True:
if v < node[0]:
if node[1] is None:
node[1] = [v, None, None]; return
node = node[1]
else:
if node[2] is None:
node[2] = [v, None, None]; return
node = node[2]
def find(self, v):
node, steps = self.root, 0
while node:
steps += 1
if v == node[0]:
return steps
node = node[1] if v < node[0] else node[2]
return steps
def height(self):
# Iterative on purpose: the degenerate tree below is 1000 nodes
# deep, and a recursive height() hits Python's stack limit on it
# -- itself a fair demonstration of what an unbalanced tree costs.
best, stack = 0, [(self.root, 1)]
while stack:
node, d = stack.pop()
if node is None:
continue
best = max(best, d)
stack.append((node[1], d + 1))
stack.append((node[2], d + 1))
return best
def inorder(self):
out, stack, node = [], [], self.root
while stack or node:
while node:
stack.append(node)
node = node[1]
node = stack.pop()
out.append(node[0])
node = node[2]
return out
import math
import random
n = 1000
orders = {
"random insert": random.Random(6).sample(range(n), n),
"sorted insert": list(range(n)),
"reversed insert": list(range(n))[::-1],
}
print("%-18s %10s %14s %18s" % ("insertion order", "height", "log2(n)",
"steps to find last"))
for name, seq in orders.items():
t = BST()
for v in seq:
t.insert(v)
print("%-18s %10d %14.1f %18d" % (
name, t.height(), math.log2(n), t.find(seq[-1])))
# Sorted input is not an adversarial case anybody has to construct. It is
# what you get from a database export, a sorted file, an auto-increment
# id, a timestamp column -- and it turns the tree into a linked list. The
# height is n, not log n, and every search walks the whole thing.
#
# The tree is still CORRECT: it is still a BST, and in-order traversal
# still gives sorted output. It is only the performance that collapsed,
# which is why the bug survives testing.
t = BST()
for v in [5, 3, 8, 1, 4]:
t.insert(v)
print()
print("in-order traversal of any BST is sorted:", t.inorder())
deg = BST()
for v in range(6):
deg.insert(v)
print("...including the degenerate one: ", deg.inorder())
# What a self-balancing tree adds is a rotation after each insert that
# keeps the height at O(log n) whatever the input order. The cost is a
# constant factor on writes; the benefit is that the worst case stops
# being reachable by ordinary data.
print()
print("%8s %12s %16s %14s" % ("n", "balanced", "degenerate", "ratio"))
for n in (1000, 10000, 100000, 1000000):
bal, degn = math.log2(n), n / 2
print("%8d %12.1f %16.0f %14.0fx" % (n, bal, degn, degn / bal))
# At a million rows the difference between a balanced tree and a sorted
# insert order is twenty steps against half a million. That is the entire
# argument for red-black and AVL trees, and it is why the ordered
# containers in every standard library use one.
Output
Guided tour
Insert a few values and watch each one walk down the tree, going left or right at every comparison.
Search for something. The highlighted path shows roughly half the remaining tree being discarded at each step.
Press In-order traversal. The values come out perfectly sorted — that is the BST rule paying off.
Press Sorted input. The tree collapses into a straight line and the height jumps to n — every search is now linear.
Delete a node with two children and note which value replaces it: the in-order successor, the only choice that keeps the ordering intact.
In one line
A BST turns the binary-search idea into a living structure with O(log n) search, insert and delete — but only while it stays bushy. Sorted input degenerates it to a linked list, which is precisely why self-balancing variants exist and why they, not plain BSTs, are what production libraries ship.
Deletion, the awkward operation
Insertion and search are straightforward. Deletion has three cases, and the third is where implementations go wrong.
A leaf. Remove it.
One child. Replace the node with its child.
Two children. Replace the node's value with its in-order successor — the smallest value in its right subtree — then delete that successor, which by construction has at most one child.
def delete(node, value):
if not node:
return None
if value < node.value:
node.left = delete(node.left, value)
elif value > node.value:
node.right = delete(node.right, value)
else:
if not node.left:
return node.right
if not node.right:
return node.left
succ = node.right # find the in-order successor
while succ.left:
succ = succ.left
node.value = succ.value
node.right = delete(node.right, succ.value)
return node
The predecessor (largest in the left subtree) works equally well. Either choice preserves the ordering invariant, which is what matters.
Note that repeated deletions can unbalance a tree even if insertions were balanced — another argument for a self-balancing implementation.
Where trees beat hash tables
Need
Structure
Lookup by exact key
Hash table — O(1)
Range queries
Tree
Sorted iteration
Tree
Nearest key
Tree
Minimum or maximum
Tree, or a heap
Predictable worst case
Balanced tree — O(log n) guaranteed
The last row is worth noting: a hash table's O(1) is an average, with an O(n) worst case; a balanced tree's O(log n) is a guarantee. For latency-sensitive systems that certainty sometimes wins.
In Python specifically, there is no built-in balanced tree. The practical alternatives are dict for unordered lookup, bisect on a sorted list for range queries when insertions are rare, and the third-party sortedcontainers package, which provides sorted list, dict and set types with excellent constant factors.
B-trees, and why databases use them
A B-tree node holds many keys — hundreds — rather than one, so the tree is very shallow: a few levels for millions of records.
The reason is disk. Reading from disk or SSD happens in pages of several kilobytes, and the cost is dominated by the number of page reads rather than the comparisons within a page. A binary tree with a million nodes is 20 levels deep, meaning up to 20 page reads. A B-tree with 200 keys per node is 3 levels deep — 3 reads.
That is why every relational database index is a B-tree (usually a B+ tree, with all values in the leaves and the leaves linked for range scans). It is the same ordering invariant, restructured around the hardware.
Questions people ask
Why not always use a hash table? Because it has no order. Range queries, sorted iteration and nearest-key lookups all need a tree.
What makes a tree balanced? Height O(log n). AVL and red-black trees enforce it with rotations on insertion and deletion.
What happens with sorted insertions? An unbalanced tree degrades to a linked list — O(n) operations. This is common in practice, not a corner case.
How do I do a range query? Traverse in order, pruning subtrees entirely outside the range.
Does Python have a balanced tree? Not in the standard library. Use bisect on a sorted list, or sortedcontainers.
What is the difference between a BST and a heap? A BST orders left-node-right for sorted access; a heap only orders parent against children, giving O(1) access to the extreme value and no ordering otherwise.
Recap in one screen
Left subtree smaller, right subtree larger — that invariant gives O(log n) search on a balanced tree.
An in-order traversal yields sorted values, which is what hash tables cannot do.
Sorted insertions produce a degenerate O(n) tree, so self-balancing (AVL, red-black) is what production uses.
Deletion with two children replaces the node with its in-order successor.
B-trees widen the nodes to match disk pages, which is why every database index is one.
Run it in Python
Insert, search, in-order traversal and delete — including the two-child delete that everyone gets wrong. The last block inserts sorted keys to show the tree collapsing into a linked list.
bst.pyPython 3
# A binary search tree: everything left is smaller, everything right larger.
class Node:
def __init__(self, key):
self.key = key
self.left = self.right = None
def insert(node, key):
if node is None:
return Node(key)
if key < node.key:
node.left = insert(node.left, key) # rebuild the link on the way out
elif key > node.key:
node.right = insert(node.right, key)
return node # equal keys: ignored
def search(node, key, depth=1):
if node is None:
return None, depth
if key == node.key:
return node, depth
if key < node.key:
return search(node.left, key, depth + 1)
return search(node.right, key, depth + 1)
def inorder(node, out=None):
if out is None:
out = []
if node:
inorder(node.left, out) # left
out.append(node.key) # self
inorder(node.right, out) # right
return out
def height(node):
return 0 if node is None else 1 + max(height(node.left), height(node.right))
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: # 0 or 1 child: promote it
return node.right
if node.right is None:
return node.left
successor = node.right # 2 children: smallest on the right
while successor.left:
successor = successor.left
node.key = successor.key # copy it up
node.right = delete(node.right, successor.key)
return node
root = None
for key in [50, 30, 70, 20, 40, 60, 80]:
root = insert(root, key)
print("in-order :", inorder(root), " <- always sorted")
print("height :", height(root))
for key in (40, 65):
node, depth = search(root, key)
print(f"search {key}: {'found' if node else 'not found'} after {depth} comparisons")
root = delete(root, 30) # one child
root = delete(root, 50) # two children - the interesting case
print("after deleting 30 and 50:", inorder(root))
print()
degenerate = None
for key in [10, 20, 30, 40, 50, 60, 70]: # sorted input
degenerate = insert(degenerate, key)
print("sorted input -> height", height(degenerate), "for 7 nodes")
print("That is a linked list. Search is O(n), and this is why AVL and")
print("red-black trees exist.")
Output
How the code works
node.left = insert(node.left, key)Assigning the result back is what builds the tree. The recursive call returns either the existing subtree or a brand-new node, and this line does not need to know which.
if key < node.key: ... else: rightOne comparison discards an entire subtree, exactly like binary search on an array — the tree is that algorithm made into a structure that can also be inserted into cheaply.
inorder: left, self, rightVisiting in that order emits the keys in sorted order, for free and without sorting anything. Change the position of the append and you have pre-order or post-order instead.
successor = node.right; while successor.left:Deleting a node with two children means finding the next key in sorted order — the leftmost node of the right subtree — copying it up, and deleting that instead. It is guaranteed to have at most one child, so the hard case reduces to an easy one.
sorted input -> height 7A BST's O(log n) is a property of its shape, not its definition. Sorted input produces one long spine, and every operation degrades to O(n). Self-balancing trees exist entirely to prevent this.
Change one thing
Insert [50, 30, 70, ...] shuffled with random.shuffle and print the height each time. Random order gives O(log n) with high probability — that is the usual defence.
Delete a leaf, a one-child node and the root, and print the traversal after each. It stays sorted, which is the invariant to test against.
Add a count to each node instead of ignoring duplicate keys. That is how a BST becomes a multiset.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Inserting sorted keys into a plain BST produces:
Every key goes right, so the tree is one spine and search degrades to O(n). The program prints height 7 for seven sorted keys.
An in-order traversal of a BST emits the keys:
Left, self, right. It comes out sorted for free, without sorting anything - which is the structure's whole selling point over a hash table.
Deleting a node with two children works by:
The leftmost node of the right subtree has at most one child, so the hard case reduces to an easy one.
Cheat sheet
Binary Search Trees
Smaller on the left, larger on the right — one rule that turns search into a series of halvings. Then insert sorted data and watch the whole structure collapse into a linked list.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.